Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time

DOI10.1145/2746539.2746588zbMath1321.05268OpenAlexW2064493067MaRDI QIDQ2941562

Ken-ichi Kawarabayashi, Mikkel Thorup

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746588

zbMATH Keywords

minimum cutedge connectivitysimple graphsdeterministic near-linear time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (14)

Minimum Cuts in Surface Graphs ⋮ Cache Oblivious Minimum Cut ⋮ On Element-Connectivity Preserving Graph Simplification ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Unnamed Item ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Practical Minimum Cut Algorithms ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finding a small vertex cut on distributed networks

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item

This page was built for publication: Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time