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

DOI10.4230/LIPICS.SOCG.2016.22zbMATH Open1387.05054arXiv1411.7055OpenAlexW2963719527MaRDI QIDQ3132856FDOQ3132856

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

Publication date: 30 January 2018

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)}$.

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

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

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)

Cited In (12)

• NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
• Title not available (Why is that?)
• 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
• 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
• Global minimum cuts in surface embedded graphs
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• 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)