Disjoint Cycles: Integrality Gap, Hardness, and Approximation

DOI10.1007/11496915_5zbMath1119.05103OpenAlexW1497071043MaRDI QIDQ3596365

Mohammad R. Salavatipour, Jacques Verstraete

Publication date: 30 August 2007

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11496915_5

Mathematics Subject Classification ID

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

Related Items (7)

Packing cycles exactly in polynomial time ⋮ The transposition median problem is NP-complete ⋮ Approximability of Packing Disjoint Cycles ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Packing disjoint cycles over vertex cuts ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs

This page was built for publication: Disjoint Cycles: Integrality Gap, Hardness, and Approximation