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

DOI10.1016/j.orl.2004.12.001zbMath1080.05091OpenAlexW2009614765WikidataQ57702315 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 optimizationsparse graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs, Theoretical and computational advances for network diversion, An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs

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