NP-Completeness of Some Tree-Clustering Problems
Schreiber, Falk and Skodinis, Konstantinos (1998) NP-Completeness of Some Tree-Clustering Problems. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 288-301 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_22).
Full text not available from this repository.
A graph is a tree of paths (cycles), if its vertex set can be partitioned into clusters, such that each cluster induces a simple path (cycle), and the clusters form a tree. Our main result states that the problem whether or not a given graph is a tree of paths (cycles) is NP-complete. Moreover, if the length of the paths (cycles) is bounded by a constant, the problem is in P.
Repository Staff Only: item control page