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

Datalogisk Institut

12 Citationer (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).

Originalsprog	Engelsk
Titel	32nd International Symposium on Computational Geometry (SoCG 2016)
Redaktører	Sandor Fekete, Anna Lubiw
Antal sider	16
Forlag	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato	1 jun. 2016
ISBN (Elektronisk)	978-3-95977-009-5
DOI	https://doi.org/10.4230/LIPIcs.SoCG.2016.22
Status	Udgivet - 1 jun. 2016
Begivenhed	International Symposium on Computational Geometry (SoCG 2016) - Boston, MA, USA Varighed: 14 jun. 2016 → 18 jun. 2016 Konferencens nummer: 32

Konference

Konference	International Symposium on Computational Geometry (SoCG 2016)
Nummer	32
Land/Område	USA
By	Boston, MA
Periode	14/06/2016 → 18/06/2016

Navn	Leibniz International Proceedings in Informatics
Vol/bind	51
ISSN	1868-8969

Adgang til dokumentet

10.4230/LIPIcs.SoCG.2016.22Licens: CC BY

Borradaile_2016_All-pairs_minimumForlagets udgivne version, 581 KBLicens: CC BY

Citationsformater

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

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). red. / Sandor Fekete; Anna Lubiw. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. (Leibniz International Proceedings in Informatics, Bind 51).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Borradaile, G, Eppstein, D, Nayyeri, A & Wulff-Nilsen, C 2016, All-pairs minimum cuts in near-linear time for surface-embedded graphs. i S Fekete & A Lubiw (red), 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, bind 51, International Symposium on Computational Geometry (SoCG 2016), Boston, MA, USA, 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. I Fekete S, Lubiw A, red., 32nd International Symposium on Computational Geometry (SoCG 2016). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. (Leibniz International Proceedings in Informatics, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater