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

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

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.

Bibliographic Details
Published in:SIAM journal on computing. 26, 3 (1997).
Main Author: Thomassen, Carsten
Format: Article
Language:English
Subjects:
Complexity.
Minimum cycle cover.