The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs

DOI10.1137/S0895480190177042zbMath0823.90038OpenAlexW1965690159WikidataQ29398332 ScholiaQ29398332MaRDI QIDQ4307048

Russell Mardon, David B. Hartvigsen

Publication date: 24 October 1994

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480190177042

zbMATH Keywords

minimum cycle basisall-pairs min cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Paths and cycles (05C38)

Related Items

Minimum cycle bases of weighted outerplanar graphs, The planar multiterminal cut problem, New approximation algorithms for minimum cycle bases of graphs, Cycle bases in graphs characterization, algorithms, complexity, and applications, Characterization of minimum cycle basis in weighted partial 2-trees, An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs, Properties of Gomory-Hu co-cycle bases, Faster Approximate Diameter and Distance Oracles in Planar Graphs, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time