Packing cycles in undirected graphs
DOI10.1016/S0196-6774(03)00052-XzbMATH Open1084.05067OpenAlexW2091737416MaRDI QIDQ4458879FDOQ4458879
Authors: Alberto Caprara, Alessandro Panconesi, Romeo Rizzi
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
Recommendations
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (34)
- Approximability of Packing Disjoint Cycles
- Approximation algorithms and hardness results for cycle packing problems
- Packing edge-disjoint cycles in graphs and the cyclomatic number
- Finding Local Genome Rearrangements
- Packing disjoint cycles over vertex cuts
- A note on disjoint cycles
- Approximation algorithms for grooming in optical network design
- Approximability of packing disjoint cycles
- Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs
- Minimum weakly fundamental cycle bases are hard to find
- Efficient approximation algorithms for shortest cycles in undirected graphs
- An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
- A branch-price-and-cut algorithm for packing cuts in undirected graphs
- Packing Arc-Disjoint Cycles in Tournaments
- Packing cycles in graphs. II
- Packing cycles through prescribed vertices under modularity constraints
- Maximum cycle packing using SPR-trees
- Disjoint cycles intersecting a set of vertices
- Maximum cycle packing in Eulerian graphs using local traces
- Induced packing of odd cycles in planar graphs
- Deriving compact extended formulations via LP-based separation techniques
- Packing directed cycles efficiently
- Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
- Approximation algorithms for cycle packing problems
- Half-integral packing of odd cycles through prescribed vertices
- Packing cycles through prescribed vertices
- Disjoint Cycles: Integrality Gap, Hardness, and Approximation
- CTL Model-Checking with Graded Quantifiers
- Packing arc-disjoint cycles in tournaments
- Title not available (Why is that?)
- Deriving compact extended formulations via LP-based separation techniques
- Packing Euler graphs with traces
This page was built for publication: Packing cycles in undirected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4458879)