An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)

DOI10.1007/s00453-017-0313-5zbMath1386.05149arXiv1510.03945OpenAlexW2608681412WikidataQ59603389 ScholiaQ59603389MaRDI QIDQ1751097

Dimitris Chatzidimitriou, Ignasi Sau, Jean-Florent Raymond, Dimitrios M. Thilikos

Publication date: 23 May 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1510.03945

zbMATH Keywords

approximation algorithmsErdős-Pósa propertycoverings in graphspackings in graphsminor-models of \(\theta _{r}\)protrusion decomposition

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (6)

A Tight Erdös--Pósa Function for Wheel Minors ⋮ Erdös--Pósa from Ball Packing ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ Packing and Covering Induced Subdivisions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An edge variant of the Erdős-Pósa property
• The Erdős-Pósa property for clique minors in highly connected graphs
• Kernel bounds for disjoint cycles and disjoint paths
• Disjoint cycles intersecting a set of vertices
• The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
• Efficient algorithms for decomposing graphs under degree constraints
• The Erdös-Pósa property for matroid circuits
• Graph minors. V. Excluding a planar graph
• Tree-partitions of infinite graphs
• Packing directed circuits
• Edge-disjoint odd cycles in planar graphs.
• On tree-partitions of graphs
• Minors in graphs of large \(\theta_r\)-girth
• Recent techniques and results on the Erdős-Pósa property
• The Erdős-Pósa property for long circuits
• Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles
• Edge-disjoint Odd Cycles in 4-edge-connected Graphs
• Hitting Diamonds and Growing Cacti
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• Packing cycles in undirected graphs
• (Meta) Kernelization
• On Independent Circuits Contained in a Graph
• Excluded Forest Minors and the Erdős–Pósa Property
• Large-treewidth graph decompositions and applications
• Hitting and Harvesting Pumpkins
• The Erdős-Pósa property for odd cycles in highly connected graphs

This page was built for publication: An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)