Packing cycles in undirected graphs

DOI10.1016/S0196-6774(03)00052-XMaRDI QIDQ4458879zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

ApproximationComplexityEdge-disjoint cyclesLinear programming relaxationPacking

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Approximability of Packing Disjoint Cycles
• Approximability of packing disjoint cycles
• Approximation algorithms for cycle packing problems
• Approximation algorithms and hardness results for cycle packing problems
• scientific article; zbMATH DE number 1875440

Cited in

(34)

• Minimum weakly fundamental cycle bases are hard to find
• Packing cycles in graphs. II
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Half-integral packing of odd cycles through prescribed vertices
• Maximum cycle packing in Eulerian graphs using local traces
• Packing cycles through prescribed vertices
• Packing arc-disjoint cycles in tournaments
• Approximation algorithms for cycle packing problems
• CTL Model-Checking with Graded Quantifiers
• Disjoint Cycles: Integrality Gap, Hardness, and Approximation
• A note on disjoint cycles
• Packing cycles through prescribed vertices under modularity constraints
• scientific article; zbMATH DE number 1875440 (Why is no real title available?)
• Approximation algorithms and hardness results for cycle packing problems
• Maximum cycle packing using SPR-trees
• Kernelization of Arc Disjoint Cycle Packing in \alpha -Bounded Digraphs
• Packing Arc-Disjoint Cycles in Tournaments
• Finding Local Genome Rearrangements
• Packing Euler graphs with traces
• A branch-price-and-cut algorithm for packing cuts in undirected graphs
• Approximability of packing disjoint cycles
• Approximability of Packing Disjoint Cycles
• Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
• Approximation algorithms for grooming in optical network design
• Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
• Deriving compact extended formulations via LP-based separation techniques
• Deriving compact extended formulations via LP-based separation techniques
• Kernelization of arc disjoint cycle packing in -bounded digraphs
• Disjoint cycles intersecting a set of vertices
• Induced packing of odd cycles in planar graphs
• Packing directed cycles efficiently
• Packing edge-disjoint cycles in graphs and the cyclomatic number
• Packing disjoint cycles over vertex cuts
• Efficient approximation algorithms for shortest cycles in undirected graphs

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)