Weakly negative circles and best clustering in signed graphs
Congressus Numerantium · 22.06.2026 · 237 · 93-98
DOI: 10.61091/cn237-06 ↗Kurz gefasst
Fachartikel in der Zeitschrift Congressus Numerantium, online erschienen am 22.06.2026. Verfasst von Michael J. Gottstein und 2 weiteren Autor:innen.
Abstract (Originalsprache)
Clustering a signed graph means partitioning the vertices into clusters so that every positive edge, and no negative edge, is within a cluster. The obstruction to clustering is circles with exactly one negative edge (``weakly negative circles’’). The correlation clustering problem is to cluster with the minimum number \(Q\) of edges that violate the clustering rule. A lower bound is \(w\), the maximum number of edge-disjoint weakly negative circles. If every two such circles are edge disjoint, then \(Q=w\). We characterize the signed graphs in which no two weakly negative circles share any edges. A corollary is a straightforward recognition algorithm for such signed graphs. An unsolved problem is to characterize the signed graphs with \(Q=w\).
Zitieren
APA
Gottstein, M. J., Parsaei-Majd, L., & Zaslavsky, T. (2026). Weakly negative circles and best clustering in signed graphs. Congressus Numerantium, 237, 93-98. https://doi.org/10.61091/cn237-06
Vancouver
Gottstein MJ, Parsaei-Majd L, Zaslavsky T. Weakly negative circles and best clustering in signed graphs. Congressus Numerantium. 2026;237:93-98. doi:10.61091/cn237-06
BibTeX
@article{Gottstein2026,
author = {Gottstein, Michael J. and Parsaei-Majd, Leila and Zaslavsky, Thomas},
title = {Weakly negative circles and best clustering in signed graphs},
journal = {Congressus Numerantium},
year = {2026},
volume = {237},
pages = {93--98},
doi = {10.61091/cn237-06}
}
EUVIMED