Min st-cut oracle for planar graphs with near-linear preprocessing time
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Min st-cut oracle for planar graphs with near-linear preprocessing time. / Borradaile, Glencora; Sankowski, Piotr; Wulff-Nilsen, Christian.
2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2010. s. 601-610.Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Min st-cut oracle for planar graphs with near-linear preprocessing time
AU - Borradaile, Glencora
AU - Sankowski, Piotr
AU - Wulff-Nilsen, Christian
N1 - Conference code: 51
PY - 2010
Y1 - 2010
N2 - For an undirected n-vertex planar 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 min st-cut in G? We show how to answer such queries in constant time with O(n log5 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Our oracle can be extended to report the min st-cuts in time proportional to their size. Since all-pairs min st-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log5 n) time and O(n log n) space and an explicit representation with additional O(C) time and space where C is the size of the basis. To obtain our results, we require that shortest paths be unique; this assumption can be removed deterministically with an additional O(log2 n) running-time factor.
AB - For an undirected n-vertex planar 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 min st-cut in G? We show how to answer such queries in constant time with O(n log5 n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Our oracle can be extended to report the min st-cuts in time proportional to their size. Since all-pairs min st-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log5 n) time and O(n log n) space and an explicit representation with additional O(C) time and space where C is the size of the basis. To obtain our results, we require that shortest paths be unique; this assumption can be removed deterministically with an additional O(log2 n) running-time factor.
KW - Algorithms
KW - Graph theory
KW - Networks
UR - http://www.scopus.com/inward/record.url?scp=78751563054&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2010.63
DO - 10.1109/FOCS.2010.63
M3 - Article in proceedings
AN - SCOPUS:78751563054
SN - 978-1-4244-8525-3
SP - 601
EP - 610
BT - 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS)
PB - IEEE
Y2 - 23 October 2010 through 26 October 2010
ER -
ID: 172852723