EUVIMEDEUVIMED entdecken
Crossref

Weakly negative circles and best clustering in signed graphs

Michael J. Gottstein, Leila Parsaei-Majd, Thomas Zaslavsky

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →