Approximability of packing disjoint cycles

DOI10.1007/s00453-009-9349-5zbMath1213.05245OpenAlexW2043985142MaRDI QIDQ534781

Mohammad R. Salavatipour, Zachary Friggstad

Publication date: 10 May 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

ApproximationEdge-disjoint pathsEdge-disjoint cyclesHardness of approximationIntegrality gap

Mathematics Subject Classification ID

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

Related Items (3)

A note on disjoint cycles ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Maximum cycle packing using SPR-trees

Cites Work

• 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
• Packing cycles in undirected graphs
• Packing Digraphs with Directed Closed Trails
• Approximation algorithms and hardness results for cycle packing problems
• Approximability of Packing Disjoint Cycles
• 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