Packing cycles in undirected graphs

DOI10.1016/S0196-6774(03)00052-XzbMath1084.05067OpenAlexW2091737416MaRDI QIDQ4458879

Romeo Rizzi, Alberto Caprara, Alessandro Panconesi

Publication date: 14 March 2004

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0196-6774(03)00052-x

zbMATH Keywords

ComplexityPackingApproximationEdge-disjoint cyclesLinear programming relaxation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) 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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (27)

Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs ⋮ Packing arc-disjoint cycles in tournaments ⋮ Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs ⋮ A note on disjoint cycles ⋮ Packing cycles through prescribed vertices under modularity constraints ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ CTL Model-Checking with Graded Quantifiers ⋮ Approximability of Packing Disjoint Cycles ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\) ⋮ Deriving compact extended formulations via LP-based separation techniques ⋮ Approximability of packing disjoint cycles ⋮ Packing edge-disjoint cycles in graphs and the cyclomatic number ⋮ Half-integral packing of odd cycles through prescribed vertices ⋮ Maximum cycle packing in Eulerian graphs using local traces ⋮ 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 ⋮ Efficient approximation algorithms for shortest cycles in undirected graphs ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Induced packing of odd cycles in planar graphs ⋮ Finding Local Genome Rearrangements ⋮ Maximum cycle packing using SPR-trees ⋮ Unnamed Item ⋮ A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs

This page was built for publication: Packing cycles in undirected graphs