On packing shortest cycles in graphs

作     者：Rautenbach, Dieter Regen, Friedrich 

作者机构：Tech Univ Ilmenau Inst Math D-98684 Ilmenau Germany 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2009年第109卷第14期

页      面：816-821页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Algorithms Approximation algorithms Combinatorial problems Graph algorithms Shortest cycles Packing Complexity 

摘      要：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 is an element of {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. (C) 2009 Elsevier B.V. All rights reserved.