On packing shortest cycles in graphs

DOI10.1016/J.IPL.2009.04.001MaRDI QIDQ989491zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Friedrich Regen

Publication date 20 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2009.04.001

zbMATH Keywords

algorithmscomplexityapproximation algorithmsgraph algorithmspackingcombinatorial problemsshortest cycles

Mathematics Subject Classification ID

Approximation algorithms (68W25) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On maximal independent sets of vertices in claw-free graphs
• Packing triangles in bounded degree graphs.
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(9)

• Maximum cycle packing using SPR-trees
• Improved approximation bounds for the minimum rainbow subgraph problem
• Inapproximability of \(H\)-transversal/packing
• Packing cycles in graphs. II
• On maximum cycle packings in polyhedral graphs
• Packing edge-disjoint cycles in graphs and the cyclomatic number
• Shortest \((A+B)\)-path packing via hafnian
• Packing disjoint cycles over vertex cuts
• Packing directed cycles efficiently

This page was built for publication: On packing shortest cycles in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q989491)