Odd cycle packing

DOI10.1145/1806689.1806785MaRDI QIDQ2875196zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Bruce Reed

Publication date 13 August 2014

Published in Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1806689.1806785

zbMATH Keywords

packingodd cycle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A nearly linear time algorithm for the half integral parity disjoint paths packing problem
• Approximability of Packing Disjoint Cycles
• Approximation algorithms and hardness results for cycle packing problems
• scientific article; zbMATH DE number 6297714
• Approximability of packing disjoint cycles

Cited in

(26)

• Modification to Planarity is Fixed Parameter Tractable
• Packing cycles faster than Erdős-Pósa
• Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
• Finding odd cycle transversals.
• Edge-disjoint odd cycles in 4-edge-connected graphs
• Edge-disjoint odd cycles in 4-edge-connected graphs
• Graph minors and parameterized algorithm design
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• Chordless Cycle Packing Is Fixed-Parameter Tractable
• Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
• QPTAS and subexponential algorithm for maximum clique on disk graphs
• Packing Odd Circuits
• Induced packing of odd cycles in planar graphs
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• An Improved Algorithm for Finding Cycles Through Elements
• Confronting intractability via parameters
• Packing odd circuits in Eulerian graphs
• Solving the stable set problem in terms of the odd cycle packing number
• Weak duality for packing edge-disjoint odd \((u, v)\)-trails
• Irrelevant vertices for the planar disjoint paths problem
• Parity linkage and the Erdős-Pósa property of odd cycles through prescribed vertices in highly connected graphs
• Combing a Linkage in an Annulus
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• The maximum 3-star packing problem in claw-free cubic graphs
• Tight bounds for linkages in planar graphs
• Computing paths of large rank in planar frameworks deterministically

This page was built for publication: Odd cycle packing

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