On packing shortest cycles in graphs

DOI10.1016/j.ipl.2009.04.001zbMath1197.05119OpenAlexW2159067821MaRDI QIDQ989491

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

complexityalgorithmscombinatorial problemspackinggraph algorithmsapproximation algorithmsshortest cycles

Mathematics Subject Classification ID

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

Related Items (5)

Inapproximability of $H$-Transversal/Packing ⋮ Improved approximation bounds for the minimum rainbow subgraph problem ⋮ Packing edge-disjoint cycles in graphs and the cyclomatic number ⋮ Packing disjoint cycles over vertex cuts ⋮ Maximum cycle packing using SPR-trees

Cites Work

• Unnamed Item
• Unnamed Item
• On maximal independent sets of vertices in claw-free graphs
• Packing triangles in bounded degree graphs.
• The NP-Completeness of Some Edge-Partition Problems

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