The Karger-Stein algorithm is optimal for k-cut

DOI10.1145/3357713.3384285OpenAlexW3034552259MaRDI QIDQ5144935

Anupam Gupta, Euiwoong Lee, Jason Li

Publication date: 19 January 2021

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

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

zbMATH Keywords

minimum cutgraph algorithmsrandomized algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (5)

Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

This page was built for publication: The Karger-Stein algorithm is optimal for k-cut