Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time.
Research output: Working paper › Research
Standard
Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time. / Wulff-Nilsen, Christian.
2009. p. 1-47.Research output: Working paper › Research
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - UNPB
T1 - Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time.
AU - Wulff-Nilsen, Christian
PY - 2009
Y1 - 2009
N2 - A minimum cycle basis of a weighted undirected graph G is a ba-sis of the cycle space of G such that the total weight of the cycles inthis basis is minimized. If G is a planar graph with non-negative edgeweights, such a basis can be found in O(n2) time and space, where nis the size of G. We show that this is optimal if an explicit represen-tation of the basis is required. We then present an O(n3/2 log n) timeand O(n3/2) space algorithm that computes a minimum cycle basisimplicitly. From this result, we obtain an output-sensitive algorithmthat explicitly computes a minimum cycle basis in O(n3/2 log n + C)time and O(n3/2 + C) space, where C is the total size (number ofedges and vertices) of the cycles in the basis. These bounds reduceto O(n3/2 log n) and O(n3/2), respectively, when G is unweighted. Weget similar results for the all-pairs min cut problem since it is dualequivalent to the minimum cycle basis problem for planar graphs.We also obtain O(n3/2 log n) time and O(n3/2) space algorithms forfinding, respectively, the weight vector and a Gomory-Hu tree of G.The previous best time and space bound for these two problems wasquadratic. From our Gomory-Hu tree algorithm, we obtain the fol-lowing result: with O(n3/2 log n) time and O(n3/2) space for prepro-cessing, the weight of a min cut between any two given vertices of Gcan be reported in constant time. Previously, such an oracle requiredquadratic time and space for preprocessing. The oracle can also beextended to report the actual cut in time proportional to its size.
AB - A minimum cycle basis of a weighted undirected graph G is a ba-sis of the cycle space of G such that the total weight of the cycles inthis basis is minimized. If G is a planar graph with non-negative edgeweights, such a basis can be found in O(n2) time and space, where nis the size of G. We show that this is optimal if an explicit represen-tation of the basis is required. We then present an O(n3/2 log n) timeand O(n3/2) space algorithm that computes a minimum cycle basisimplicitly. From this result, we obtain an output-sensitive algorithmthat explicitly computes a minimum cycle basis in O(n3/2 log n + C)time and O(n3/2 + C) space, where C is the total size (number ofedges and vertices) of the cycles in the basis. These bounds reduceto O(n3/2 log n) and O(n3/2), respectively, when G is unweighted. Weget similar results for the all-pairs min cut problem since it is dualequivalent to the minimum cycle basis problem for planar graphs.We also obtain O(n3/2 log n) time and O(n3/2) space algorithms forfinding, respectively, the weight vector and a Gomory-Hu tree of G.The previous best time and space bound for these two problems wasquadratic. From our Gomory-Hu tree algorithm, we obtain the fol-lowing result: with O(n3/2 log n) time and O(n3/2) space for prepro-cessing, the weight of a min cut between any two given vertices of Gcan be reported in constant time. Previously, such an oracle requiredquadratic time and space for preprocessing. The oracle can also beextended to report the actual cut in time proportional to its size.
M3 - Working paper
SP - 1
EP - 47
BT - Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time.
ER -
ID: 18273475