Minimum Cuts of Simple Graphs in Almost Always Linear Time

DOI10.1007/978-3-642-00202-1_20zbMath1211.05064OpenAlexW2121689548MaRDI QIDQ3605499

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

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Cites Work

• Graph connectivity and its augmentation: Applications of MA orderings
• An efficient algorithm for the minimum capacity cut problem
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Implementing an efficient minimum capacity cut algorithm
• A matroid approach to finding edge connectivity and packing arborescences
• A simple and fast min-cut algorithm
• Maximal Flow Through a Network
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A new approach to the minimum cut problem
• A simple min-cut algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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