Title of article
Computational complexity of covering cyclic graphs Original Research Article
Author/Authors
Ji??? Fiala، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
8
From page
87
To page
94
Abstract
We show that the problem of covering cycles with loops, defined in Kratochvı́l et al. (Graph-Theoretical Concepts in Computer Science, Proceedings of the 23rd WG ’97, Berlin, Lecture Notes in Computer Science, Vol. 1335, Springer, Berlin, 1997, pp. 242–254) is NP-complete. We also prove NP-completeness of the 8-starfish cover problem, which concludes complete computational complexity characterization of k-starfish cover problems.
Journal title
Discrete Mathematics
Serial Year
2001
Journal title
Discrete Mathematics
Record number
949689
Link To Document