2026-07-26T19:56:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5914 2024-03-06T10:37:16Z ddc:004 open_access

All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs Borradaile, Glencora Eppstein, David Nayyeri, Amir Wulff-Nilsen, Christian minimum cuts surface-embedded graphs Gomory-Hu tree 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)}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Glencora Borradaile and David Eppstein and Amir Nayyeri and Christian Wulff-Nilsen 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.22 urn:nbn:de:0030-drops-59149 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode