Deterministic global minimum cut of a simple graph in near-linear time

DOI10.1145/2746539.2746588MaRDI QIDQ2941562zbMATH OpenOpenAlexFDO

Authors 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

deterministic near-linear timeedge connectivityminimum cutsimple graphs

Mathematics Subject Classification ID

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

Recommendations

• Deterministic Edge Connectivity in Near-Linear Time
• Minimum cuts in near-linear time
• scientific article; zbMATH DE number 1256719
• Fundamentals of Computation Theory
• Local flow partitioning for faster edge connectivity

Cites work

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

Cited in

(22)

• Compact cactus representations of all non-trivial min-cuts
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• LP relaxation and tree packing for minimum k-cut
• On element-connectivity preserving graph simplification
• Minimum cuts and sparsification in hypergraphs
• Local flow partitioning for faster edge connectivity
• Practical minimum cut algorithms
• A near-linear time algorithm for constructing a cactus representation of minimum cuts
• Computing exact minimum cuts without knowing the graph
• Fast and deterministic approximations for \(k\)-cut
• A cut tree representation for pendant pairs
• Local flow partitioning for faster edge connectivity
• Cache oblivious minimum cut
• A Strongly Polynomial Time Algorithm for Multicriteria Global Minimum Cuts
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)
• Fast and Deterministic Approximations for k-Cut.
• Minimum Cuts in Surface Graphs
• scientific article; zbMATH DE number 7759280 (Why is no real title available?)
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Breaking the n ^k barrier for minimum k -cut on simple graphs
• Finding a small vertex cut on distributed networks

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Deterministic global minimum cut of a simple graph in near-linear time

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