Approximate min-max relations for odd cycles in planar graphs

DOI10.1007/s10107-006-0063-7zbMath1113.05054OpenAlexW2032222063MaRDI QIDQ877199

Samuel Fiorini, Nadia Hardy, Adrian Vetta, Bruce A. Reed

Publication date: 19 April 2007

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0063-7

zbMATH Keywords

Odd cycle packingOdd cycle transversal

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation ⋮ Approximate min-max relations on plane graphs ⋮ Erdös-Pósa Property of Obstructions to Interval Graphs ⋮ Erdős–Pósa property of obstructions to interval graphs ⋮ Outerspatial 2-complexes: extending the class of outerplanar graphs to three dimensions ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Packing and covering balls in graphs excluding a minor ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Integer plane multiflow maximisation: one-quarter-approximation and gaps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Mangoes and blueberries
• A proof of the four color theorem
• Primal-dual approximation algorithms for feedback problems in planar graphs
• The four-colour theorem
• Edge-disjoint odd cycles in planar graphs.
• Packing triangles in bounded degree graphs.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A decomposition theorem for partially ordered sets
• Approximate Min-max Relations for Odd Cycles in Planar Graphs
• On Odd Cuts and Plane Multicommodity Flows
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• 2-Matchings and 2-covers of hypergraphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On Independent Circuits Contained in a Graph
• The Erdős-Pósa property for odd cycles in highly connected graphs