Minimum cut in \(O(m \log^2 n)\) time
From MaRDI portal
Publication:6614613
DOI10.1007/S00224-024-10179-7zbMATH Open1548.05268MaRDI QIDQ6614613
Shay Mozes, Paweł Gawrychowski, Oren Weimann
Publication date: 7 October 2024
Published in: Theory of Computing Systems (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A data structure for dynamic trees
- A matroid approach to finding edge connectivity and packing arborescences
- Random sampling in cut, flow, and network design problems
- Random sampling in cut, flow, and network design problems
- Maintaining information in fully dynamic trees with top trees
- Beyond the flow decomposition barrier
- Edge-Disjoint Spanning Trees of Finite Graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- A new approach to the maximum-flow problem
- Multi-Terminal Network Flows
- On the Alias Method for Generating Random Variables from a Discrete Distribution
- A unifying look at data structures
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- A Faster Deterministic Maximum Flow Algorithm
- A randomized linear-time algorithm to find minimum spanning trees
- A new approach to the minimum cut problem
- Local Flow Partitioning for Faster Edge Connectivity
- Deterministic Edge Connectivity in Near-Linear Time
- Fast Approximation Algorithms for Fractional Packing and Covering Problems
- Weighted min-cut: sequential, cut-query, and streaming algorithms
- Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
- Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
- Minimum cuts in near-linear time
- Max flows in O(nm) time, or better
- A note on a recent algorithm for minimum cut
- Deterministic near-linear time minimum cut in weighted graphs
This page was built for publication: Minimum cut in \(O(m \log^2 n)\) time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6614613)
