On packing shortest cycles in graphs |
| |
Authors: | Dieter Rautenbach Friedrich Regen |
| |
Affiliation: | Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany |
| |
Abstract: | We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3. |
| |
Keywords: | Algorithms Approximation algorithms Combinatorial problems Graph algorithms Shortest cycles Packing Complexity |
本文献已被 ScienceDirect 等数据库收录! |
|