The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
Authors:
- David HartvigsenDHDavid Hartvigsen
- Russell MardonRMRussell Mardon
- 1 May 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 7 (3) , 403-418
Abstract
The all-pairs min cut (APMC) problem on a nonnegative weighted graph is the problem of finding, for every pair of nodes, the min cut separating the pair. It is shown that on planar graphs, the APMC problem is equivalent to another problem, the minimum cycle basis (MCB)problem, on the dual graph. This is shown by characterizing the structure of MCBs on planar graphs in several ways. This leads to a new algorithm for solving both of these problems on planar graphs. The complexity of this algorithm equals that of the best algorithm for either problem, but is simpler.Keywords
This publication has 21 references indexed in Scilit:
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar NetworksSIAM Journal on Computing, 1985
- A linear algorithm for embedding planar graphs using PQ-treesJournal of Computer and System Sciences, 1985
- Algorithms for Generating Fundamental Cycles in a GraphACM Transactions on Mathematical Software, 1982
- Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility methodProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1976
- An algorithm for the longest cycle problemNetworks, 1976
- Graph theory and molecular orbitals. VII. The role of resonance structuresThe Journal of Chemical Physics, 1974
- On optimally sparse cycle and coboundary basis for a linear graphIEEE Transactions on Circuit Theory, 1973
- Multi-Terminal Network FlowsJournal of the Society for Industrial and Applied Mathematics, 1961
- A note on two problems in connexion with graphsNumerische Mathematik, 1959