A fast algorithm for minimum weight odd circuits and cuts in planar graphs

DOI10.1016/j.orl.2004.12.001zbMath1080.05091WikidataQ57702315 ScholiaQ57702315MaRDI QIDQ813970

Adam N. Letchford, Nicholas A. Pearson

Publication date: 2 February 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.12.001

zbMATH Keywords

combinatorial optimization; sparse graphs

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

65F20: Numerical solutions to overdetermined systems, pseudoinverses

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Exploiting planarity in separation routines for the symmetric traveling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Decomposition and optimization over cycles in binary matroids
• Weakly bipartite graphs and the max-cut problem
• Geometric algorithms and combinatorial optimization
• Parallel concepts in graph theory
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Set packing relaxations of some integer programs
• Implementing an efficient minimum capacity cut algorithm
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• A new approach to the maximum-flow problem
• A Separator Theorem for Planar Graphs
• Odd Minimum Cut-Sets and b-Matchings
• On the cut polytope
• Hamilton Paths in Grid Graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Faster shortest-path algorithms for planar graphs