On computing minimum\((s,t)\)-cuts in digraphs

DOI10.1016/j.ipl.2004.11.006zbMath1173.68611OpenAlexW1566103542MaRDI QIDQ835038

Hiroshi Nagamochi

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.11.006

zbMATH Keywords

digraphsgraph algorithmssparsificationedge connectivitymaximum flowsminimum cuts

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Random sampling in residual graphs
• On the structure of all minimum cuts in a network and applications
• Minimum cuts and related problems
• Network Flow and Testing Graph Connectivity
• Flows in Undirected Unit Capacity Networks

This page was built for publication: On computing minimum\((s,t)\)-cuts in digraphs