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

Glencora Borradaile; David Eppstein; Amir Nayyeri; Christian Wulff-Nilsen

doi:10.4230/LIPIcs.SoCG.2016.22

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

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

Department of Computer Science

12 Citations (Scopus)

25 Downloads (Pure)

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³ 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(g2).

Original language	English
Title of host publication	32nd International Symposium on Computational Geometry (SoCG 2016)
Editors	Sandor Fekete, Anna Lubiw
Number of pages	16
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date	1 Jun 2016
ISBN (Electronic)	978-3-95977-009-5
DOIs	https://doi.org/10.4230/LIPIcs.SoCG.2016.22
Publication status	Published - 1 Jun 2016
Event	International Symposium on Computational Geometry (SoCG 2016) - Boston, MA, United States Duration: 14 Jun 2016 → 18 Jun 2016 Conference number: 32

Conference

Conference	International Symposium on Computational Geometry (SoCG 2016)
Number	32
Country/Territory	United States
City	Boston, MA
Period	14/06/2016 → 18/06/2016

Series	Leibniz International Proceedings in Informatics
Volume	51
ISSN	1868-8969

Access to Document

10.4230/LIPIcs.SoCG.2016.22Licence: CC BY

Borradaile_2016_All-pairs_minimumFinal published version, 581 KBLicence: CC BY

Cite this

All-pairs minimum cuts in near-linear time for surface-embedded graphs. / Borradaile, Glencora; Eppstein, David; Nayyeri, Amir et al.
32nd International Symposium on Computational Geometry (SoCG 2016). ed. / Sandor Fekete; Anna Lubiw. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. (Leibniz International Proceedings in Informatics, Vol. 51).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Borradaile, G, Eppstein, D, Nayyeri, A & Wulff-Nilsen, C 2016, All-pairs minimum cuts in near-linear time for surface-embedded graphs. in S Fekete & A Lubiw (eds), 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, vol. 51, International Symposium on Computational Geometry (SoCG 2016), Boston, MA, United States, 14/06/2016. https://doi.org/10.4230/LIPIcs.SoCG.2016.22

Borradaile G, Eppstein D, Nayyeri A, Wulff-Nilsen C. All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Fekete S, Lubiw A, editors, 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. (Leibniz International Proceedings in Informatics, Vol. 51). doi: 10.4230/LIPIcs.SoCG.2016.22

@inproceedings{78133643badf4747a5f344c64857d190,

title = "All-pairs minimum cuts in near-linear time for surface-embedded graphs",

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 log3 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 2O(g2).",

author = "Glencora Borradaile and David Eppstein and Amir Nayyeri and Christian Wulff-Nilsen",

year = "2016",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2016.22",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

editor = "Sandor Fekete and Anna Lubiw",

booktitle = "32nd International Symposium on Computational Geometry (SoCG 2016)",

note = "International Symposium on Computational Geometry (SoCG 2016) ; Conference date: 14-06-2016 Through 18-06-2016",

}

TY - GEN

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

AU - Borradaile, Glencora

AU - Eppstein, David

AU - Nayyeri, Amir

AU - Wulff-Nilsen, Christian

N1 - Conference code: 32

PY - 2016/6/1

Y1 - 2016/6/1

N2 - 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 log3 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 2O(g2).

AB - 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 log3 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 2O(g2).

U2 - 10.4230/LIPIcs.SoCG.2016.22

DO - 10.4230/LIPIcs.SoCG.2016.22

M3 - Article in proceedings

T3 - Leibniz International Proceedings in Informatics

BT - 32nd International Symposium on Computational Geometry (SoCG 2016)

A2 - Fekete, Sandor

A2 - Lubiw, Anna

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Symposium on Computational Geometry (SoCG 2016)

Y2 - 14 June 2016 through 18 June 2016

ER -

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

Abstract

Conference

Access to Document

Fingerprint

Cite this