All-pairs minimum cuts in near-linear time for surface-embedded graphs

DOI10.4230/LIPICS.SOCG.2016.22MaRDI QIDQ3132856zbMATH OpenOpenAlexFDO

Authors Glencora Borradaile, David Eppstein, Amir Nayyeri, Christian Wulff-Nilsen

Publication date 30 January 2018

Full work available at URL https://arxiv.org/abs/1411.7055

zbMATH Keywords

minimum cutsGomory-Hu treesurface-embedded graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)

Abstract: For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(nlo{g}^{3}n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.

Recommendations

• Global minimum cuts in surface embedded graphs
• Minimum Cuts in Surface Graphs
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• Minimum cuts and shortest homologous cycles
• All-Pairs Min-Cut in Sparse Networks

Cited in

(12)

• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Recognizing planar Laman graphs
• Approximate Gomory-Hu tree is faster than \(n-1\) maximum flows
• Generalizing the all-pairs min cut problem
• Improved bounds for shortest paths in dense distance graphs
• Minimum Cuts in Surface Graphs
• New algorithms and lower bounds for all-pairs max-flow in undirected graphs
• A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• Global minimum cuts in surface embedded graphs
• All-Pairs Min-Cut in Sparse Networks

This page was built for publication: All-pairs minimum cuts in near-linear time for surface-embedded graphs

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