The Karger-Stein algorithm is optimal for k-cut

DOI10.1145/3357713.3384285MaRDI QIDQ5144935zbMATH OpenOpenAlexFDO

Authors 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

graph algorithmsminimum cutrandomized algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(7)

• Minimum violation vertex maps and their applications to cut problems
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
• A parameterized approximation scheme for min \(k\)-cut

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144935)