Approximability of Packing Disjoint Cycles

DOI10.1007/978-3-540-77120-3_28zbMath1193.68286OpenAlexW1575996043MaRDI QIDQ5387766

Zachary Friggstad, Mohammad R. Salavatipour

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.572.3668

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Combinatorial aspects of packing and covering (05B40)

Related Items (8)

Inapproximability of $H$-Transversal/Packing ⋮ Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs ⋮ Approximability of packing disjoint cycles ⋮ Packing disjoint cycles over vertex cuts ⋮ Approximation algorithms for grooming in optical network design ⋮ Disjoint cycles intersecting a set of vertices ⋮ New tools and connections for exponential-time approximation ⋮ Induced packing of odd cycles in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complete partitions of graphs
• Packing directed circuits fractionally
• A PCP characterization of NP with optimal amortized query complexity
• Asymmetric k -center is log ^* n -hard to approximate
• Hardness of the undirected edge-disjoint paths problem
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• Packing cycles in undirected graphs
• Packing Digraphs with Directed Closed Trails
• Packing cuts in undirected graphs
• Approximation algorithms and hardness results for cycle packing problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Approximability of Packing Disjoint Cycles