The number of minimum k -cuts: improving the Karger-Stein bound

DOI10.1145/3313276.3316395zbMath1437.05222arXiv1906.00417OpenAlexW2953221689MaRDI QIDQ5212764

Jason Li, Anupam Gupta, Euiwoong Lee

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1906.00417

zbMATH Keywords

graph algorithmsextremal graph theorygraph cutsminimum \(k\)-cut

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Unnamed Item

This page was built for publication: The number of minimum k -cuts: improving the Karger-Stein bound