Approximate min-max relations for odd cycles in planar graphs
DOI10.1007/S10107-006-0063-7zbMATH Open1113.05054OpenAlexW2032222063MaRDI QIDQ877199FDOQ877199
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Approximation algorithms (68W25) Paths and cycles (05C38)
Cites Work
- Finding odd cycle transversals.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Mangoes and blueberries
- Primal-dual approximation algorithms for feedback problems in planar graphs
- The four-colour theorem
- On Independent Circuits Contained in a Graph
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- A decomposition theorem for partially ordered sets
- On Odd Cuts and Plane Multicommodity Flows
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Edge-disjoint odd cycles in planar graphs.
- 2-Matchings and 2-covers of hypergraphs
- Packing triangles in bounded degree graphs.
- A proof of the four color theorem
- The Erdős-Pósa property for odd cycles in highly connected graphs
- Title not available (Why is that?)
- Approximate Min-max Relations for Odd Cycles in Planar Graphs
Cited In (14)
- Approximate Min-max Relations for Odd Cycles in Planar Graphs
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- Approximating maximum integral multiflows on bounded genus graphs
- Edge-disjoint odd cycles in 4-edge-connected 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
- 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
- Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation
- Packing and covering balls in graphs excluding a minor
- Integer plane multiflow maximisation: one-quarter-approximation and gaps
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)
