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 , pp. 288-301(Official URL:

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-37623-2_22
Classifications: G Algorithms and Complexity > G.999 Others
M Methods > M.900 Tree
G Algorithms and Complexity > G.350 Clusters

Actions (login required)

View Item View Item