Approximate min-max relations for odd cycles in planar graphs

DOI10.1007/S10107-006-0063-7MaRDI QIDQ877199zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Nadia Hardy, Adrian Vetta, Bruce 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

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

Recommendations

• Approximate Min-max Relations for Odd Cycles in Planar Graphs
• Min-max relations for odd cycles in planar graphs
• Edge-disjoint odd cycles in planar graphs.
• Optimal packings of edge-disjoint odd cycles
• Approximate min-max relations on plane graphs

Cites work

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

Cited in

(19)

• Approximate Min-max Relations for Odd Cycles in Planar Graphs
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Odd cycle transversal on P₅-free graphs in polynomial time
• A half-integral Erdős-Pósa theorem for directed odd cycles
• Edge-disjoint odd cycles in 4-edge-connected graphs
• Approximating maximum integral multiflows on bounded genus graphs
• Erdös-Pósa Property of Obstructions to Interval Graphs
• The ratio of the numbers of odd and even cycles in outerplanar graphs
• Min-max relations for odd cycles in planar graphs
• An improved integrality gap for disjoint cycles in planar graphs
• Approximate min-max relations on plane graphs
• Optimal packings of edge-disjoint odd cycles
• Erdős–Pósa property of obstructions to interval graphs
• Outerspatial 2-complexes: extending the class of outerplanar graphs to three dimensions
• Packing and covering balls in graphs excluding a minor
• Bipartizing (pseudo-)disk graphs: approximation with a ratio better than 3
• Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
• Integer plane multiflow maximisation: one-quarter-approximation and gaps
• Packing cycles in planar and bounded-genus graphs

This page was built for publication: Approximate min-max relations for odd cycles in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877199)