On the complexity of finding a minimum cycle cover of a graph

被引：41

作者：

Thomassen, C

机构：

[1] Mathematical Institute, Technical University of Denmark

来源：

SIAM JOURNAL ON COMPUTING | 1997年 / 26卷 / 03期

关键词：

complexity; minimum cycle cover;

D O I：

10.1137/S0097539794267255

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that the problem of finding a cycle cover of smallest total length is NP-hard. This confirms a conjecture of Itai, Lipton, Papadimitriou, and Rodeh from 1981.

引用

页码：675 / 677

页数：3

共 5 条

[1]

Bondy J. A., 1990, SMALL CYCLE DOUBLE C, P21

[2] COVERING GRAPHS BY CYCLES [J].

FAN, GH .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (04) :491-496

[3] THE NP-COMPLETENESS OF EDGE-COLORING [J].

HOLYER, I .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :718-720

[4] COVERING GRAPHS BY SIMPLE CIRCUITS [J].

ITAI, A ;

LIPTON, RJ ;

PAPADIMITRIOU, CH ;

RODEH, M .

SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :746-750

[5] SMALLEST (1,2)-EULERIAN WEIGHT AND SHORTEST CYCLE COVERING [J].

ZHAO, C .

JOURNAL OF GRAPH THEORY, 1994, 18 (02) :153-160

← 1 →