Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.22
URN: urn:nbn:de:0030-drops-59149
URL: https://drops.dagstuhl.de/opus/volltexte/2016/5914/
Borradaile, Glencora ; Eppstein, David ; Nayyeri, Amir ; Wulff-Nilsen, Christian
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
| pdf-format: |
|
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(n log^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)}.
BibTeX - Entry
@InProceedings{borradaile_et_al:LIPIcs:2016:5914,
author = {Glencora Borradaile and David Eppstein and Amir Nayyeri and Christian Wulff-Nilsen},
title = {{All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5914},
URN = {urn:nbn:de:0030-drops-59149},
doi = {10.4230/LIPIcs.SoCG.2016.22},
annote = {Keywords: minimum cuts, surface-embedded graphs, Gomory-Hu tree}
}
| Keywords: | minimum cuts, surface-embedded graphs, Gomory-Hu tree | |
| Seminar: | 32nd International Symposium on Computational Geometry (SoCG 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 10.06.2016 |
