Journal article
On the complexity of finding a minimum cycle cover of a graph
In
S I a M Journal on Computing
—
1997, Volume 26, Issue 3, pp. 675-677
Abstract
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.
| Language: | English |
|---|---|
| Year: | 1997 |
| Pages: | 675-677 |
| ISSN: | 10957111 and 00975397 |
| Types: | Journal article |
| DOI: | 10.1137/S0097539794267255 |
| ORCIDs: | Thomassen, Carsten |
Keywords
