All-Pairs Min-Cut in Sparse Networks

DOI10.1006/JAGM.1998.0961MaRDI QIDQ4217302zbMATH OpenOpenAlexFDO

Authors S. R. Arikati, Shiva Chaudhuri, Christos Zaroliagis

Publication date 11 November 1998

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11858/00-001M-0000-0014-A418-4

zbMATH Keywords

all-pairs min-cut problembounded tree-width

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• All-pairs min-cut in sparse networks
• Generalizing the all-pairs min cut problem
• Sparsest cuts and bottlenecks in graphs
• All-pairs shortest paths algorithm for high-dimensional sparse graphs
• Minimum cuts and sparsification in hypergraphs
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Minimum cuts in parametric networks
• Minimal graph cuts on network subgraphs
• All-pairs minimum cuts in near-linear time for surface-embedded graphs
• Minimum cut bases in undirected networks

Cited in

(10)

• Generalizing the all-pairs min cut problem
• An exponential lower bound for cut sparsifiers in planar graphs
• On mimicking networks representing minimum terminal cuts
• All-pairs min-cut in sparse networks
• All-pairs minimum cuts in near-linear time for surface-embedded graphs
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• Faster algorithms for all-pairs bounded min-cuts
• An exponential lower bound for cut sparsifiers in planar graphs
• New algorithms and lower bounds for all-pairs max-flow in undirected graphs
• Faster algorithms for shortest path and network flow based on graph decomposition

This page was built for publication: All-Pairs Min-Cut in Sparse Networks

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