A simple and fast min-cut algorithm

DOI10.1007/S00224-007-2010-2MaRDI QIDQ2642908zbMATH OpenOpenAlexFDO

Authors Michael Brinkmeier

Publication date 6 September 2007

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-007-2010-2

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Programming involving graphs or networks (90C35)

Recommendations

• Fundamentals of Computation Theory
• A simple min-cut algorithm
• scientific article; zbMATH DE number 7759280
• A simple minimum \(T\)-cut algorithm
• scientific article; zbMATH DE number 742961
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A faster parametric minimum-cut algorithm
• scientific article; zbMATH DE number 1342143
• A fast algorithm for computing minimum 3-way and 4-way cuts
• Minimum Cuts of Simple Graphs in Almost Always Linear Time

Cited in

(20)

• A new and improved algorithm for the 3-cut problem
• The line index and minimum cut of weighted graphs
• A correctness certificate for the Stoer-Wagner min-cut algorithm
• Implementing an efficient minimum capacity cut algorithm
• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
• A min-cut approach to functional regionalization, with a case study of the Italian local labour market areas
• Efficient algorithm for finding all minimal edge cuts of a nonoriented graph
• A Linear Algorithm for Finding the Invariant Edges of an Edge-Weighted Graph
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time
• Efficient algorithms for minimum range cut problems
• A simple min-cut algorithm
• Local flow partitioning for faster edge connectivity
• Minimum cuts in near-linear time
• Fundamentals of Computation Theory
• I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs
• scientific article; zbMATH DE number 7759280 (Why is no real title available?)
• Minimum cut in \(O(m \log^2 n)\) time
• Local ratio with negative weights.
• On computing minimum(s,t)-cuts in digraphs

This page was built for publication: A simple and fast min-cut algorithm

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