On packing shortest cycles in graphs

DOI10.1016/J.IPL.2009.04.001zbMATH Open1197.05119OpenAlexW2159067821MaRDI QIDQ989491FDOQ989491

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On maximal independent sets of vertices in claw-free graphs
• The NP-Completeness of Some Edge-Partition Problems
• Packing triangles in bounded degree graphs.

Cited In (9)

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

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)