Minimum Cuts of Simple Graphs in Almost Always Linear Time

DOI10.1007/978-3-642-00202-1_20MaRDI QIDQ3605499zbMATH OpenOpenAlexFDO

Authors Michael Brinkmeier

Publication date 24 February 2009

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00202-1_20

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)

Recommendations

• Minimum cuts in near-linear time
• scientific article; zbMATH DE number 1256719
• A new approach to the minimum cut problem
• Fundamentals of Computation Theory
• A simple and fast min-cut algorithm

Cites work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A matroid approach to finding edge connectivity and packing arborescences
• A new approach to the maximum-flow problem
• A new approach to the minimum cut problem
• A simple and fast min-cut algorithm
• A simple min-cut algorithm
• An efficient algorithm for the minimum capacity cut problem
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Graph connectivity and its augmentation: Applications of MA orderings
• scientific article; zbMATH DE number 437577 (Why is no real title available?)
• scientific article; zbMATH DE number 1256719 (Why is no real title available?)
• scientific article; zbMATH DE number 1555934 (Why is no real title available?)
• scientific article; zbMATH DE number 6472607 (Why is no real title available?)
• Implementing an efficient minimum capacity cut algorithm
• Maximal Flow Through a Network
• Multi-Terminal Network Flows

Cited in

(12)

• On minimum cuts and the linear arrangement problem
• A simple and fast min-cut algorithm
• A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems
• scientific article; zbMATH DE number 3956440 (Why is no real title available?)
• An \NC Algorithm for Minimum Cuts
• scientific article; zbMATH DE number 6850341 (Why is no real title available?)
• Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph
• Minimum cuts in near-linear time
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)
• scientific article; zbMATH DE number 7759280 (Why is no real title available?)
• Breaking the n ^k barrier for minimum k -cut on simple graphs
• On finding fundamental cut sets

This page was built for publication: Minimum Cuts of Simple Graphs in Almost Always Linear Time

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