Approximation algorithms and hardness results for cycle packing problems
From MaRDI portal
Publication:4962688
DOI10.1145/1290672.1290685zbMath1446.68121OpenAlexW2060363698MaRDI QIDQ4962688
Michael Krivelevich, Mohammad R. Salavatipour, Jacques Verstraete, Raphael Yuster, Zeev Nutov
Publication date: 5 November 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1290672.1290685
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ Packing arc-disjoint cycles in tournaments ⋮ A note on disjoint cycles ⋮ Packing arc-disjoint cycles in oriented graphs ⋮ Packing cycles exactly in polynomial time ⋮ Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem ⋮ Packing cycles through prescribed vertices under modularity constraints ⋮ Minimum degree conditions for vertex-disjoint even cycles in large graphs ⋮ Approximability of Packing Disjoint Cycles ⋮ Approximability of packing disjoint cycles ⋮ Packing edge-disjoint cycles in graphs and the cyclomatic number ⋮ Half-integral packing of odd cycles through prescribed vertices ⋮ Packing Euler graphs with traces ⋮ Packing disjoint cycles over vertex cuts ⋮ Approximation algorithms for grooming in optical network design ⋮ Disjoint cycles intersecting a set of vertices ⋮ Packing cycles through prescribed vertices ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Packing Cycles Faster Than Erdos--Posa ⋮ Induced packing of odd cycles in planar graphs ⋮ Disjoint Even Cycles Packing ⋮ Maximum cycle packing using SPR-trees ⋮ Cycle decompositions and constructive characterizations ⋮ Unnamed Item ⋮ A complexity and approximation framework for the maximization scaffolding problem
