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.

Abstract

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
ID Code:336

Repository Staff Only: item control page

References

S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277-384, 1987.

F.T. Boesch and J.F. Gimpel. Covering the points of a digraph with pointdisjoint paths and its application to code optimization. J. Assoc. Comput. Mach., 24(2):192-198, 1977.

F.J. Brandenburg. Graph Clustering I: Cycles of cliques.

In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 158-168. Springer Verlag, 1997.

E. Cohen and M. Tarsi. NP-Completeness of graph decomposition problems. J. Complexity, 7:200-212, 1991.

D. Dor and M. Tarsi. Graph decomposition is np-complete: A complete proof of holyer's conjecture. SIAM J. Comput., 26(4):1166-1187, 1997.

Peter Eades and Qing-Wen Feng. Multilevel Visualization of Clustered Graphs. LNCS, 1190:101-112, 1997.

Qing-Wen Feng, Robert F. Cohen, and Peter Eades. How to draw a planar clustered graph. In COCOON '95, volume 959 of LNCS, pages 21-31. Springer-Verlag, 1995.

T.M.J. Fruchtermann and E.M. Reingold. Graph drawing by force-directed placement. Software Practice and Experience, 21(11):1129-1164, November 1991.

M.R. Garey and D.S. Johnson. Computers and Itractability: A Guide to hte theory of NP-Completeness. W.H. Freeman and company, NY, 1979.

M. Himsolt. The Graphlet System. LNCS, 1190:233-240, 1997.

I. Holyer. The np-completeness of some edge-partition problems. SIAM J. Comput., 10(4):713-717, 1981.

J. Kratochvíl, M. Goljan, and P. Kucaera. String graphs. Technical report, Academia Prague, 1986.

C.H. Papadimitriou. Computational complexity. Addison-Wesley Publishing Company, 1994.

T. Roxborough and A. Sen. Graph clustering using multiway ratio cut. In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 291-296. Springer Verlag, 1997.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man. Cybern., SMC-11(2):109-125, 1981.