NPCompleteness of Some TreeClustering ProblemsSchreiber, Falk and Skodinis, Konstantinos (1998) NPCompleteness of Some TreeClustering Problems. In: Graph Drawing 6th International Symposium, GD’ 98, August 1315, 1998 , pp. 288301(Official URL: http://dx.doi.org/10.1007/3540376232_22). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540376232_22
AbstractA 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 NPcomplete. Moreover, if the length of the paths (cycles) is bounded by a constant, the problem is in P.
Actions (login required)
