NP-completeness of some tree-clustering problems

Falk Schreiber; Konstantinos Skodinis

doi:10.1007/3-540-37623-2_22

NP-completeness of some tree-clustering problems

Falk Schreiber, Konstantinos Skodinis

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

4 Citations (Scopus)

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.

Original language	English
Title of host publication	Graph Drawing - 6th International Symposium, GD 1998, Proceedings
Editors	Sue H. Whitesides
Publisher	Springer
Pages	288-301
Number of pages	14
ISBN (Print)	3540654739, 9783540654735
DOIs	https://doi.org/10.1007/3-540-37623-2_22
Publication status	Published - 1999
Externally published	Yes
Event	Graph Drawing 1998 - Montreal, Canada Duration: 13 Aug 1998 → 15 Aug 1998 Conference number: 6th http://www.graphdrawing.org/symposia.html https://link.springer.com/book/10.1007/3-540-37623-2 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	1547
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Graph Drawing 1998
Abbreviated title	GD 1998
Country/Territory	Canada
City	Montreal
Period	13/08/98 → 15/08/98
Internet address	http://www.graphdrawing.org/symposia.html https://link.springer.com/book/10.1007/3-540-37623-2 (Proceedings)

Access to Document

10.1007/3-540-37623-2_22

Cite this

@inproceedings{3b22c5073c964a929c8892f762e457a1,

title = "NP-completeness of some tree-clustering problems",

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.",

author = "Falk Schreiber and Konstantinos Skodinis",

year = "1999",

doi = "10.1007/3-540-37623-2_22",

language = "English",

isbn = "3540654739",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "288--301",

editor = "Whitesides, {Sue H.}",

booktitle = "Graph Drawing - 6th International Symposium, GD 1998, Proceedings",

note = "Graph Drawing 1998, GD 1998 ; Conference date: 13-08-1998 Through 15-08-1998",

url = "http://www.graphdrawing.org/symposia.html, https://link.springer.com/book/10.1007/3-540-37623-2",

}

NP-completeness of some tree-clustering problems. / Schreiber, Falk; Skodinis, Konstantinos.
Graph Drawing - 6th International Symposium, GD 1998, Proceedings. ed. / Sue H. Whitesides. Springer, 1999. p. 288-301 (Lecture Notes in Computer Science ; Vol. 1547).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - NP-completeness of some tree-clustering problems

AU - Schreiber, Falk

AU - Skodinis, Konstantinos

N1 - Conference code: 6th

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84957880064&partnerID=8YFLogxK

U2 - 10.1007/3-540-37623-2_22

DO - 10.1007/3-540-37623-2_22

M3 - Conference Paper

AN - SCOPUS:84957880064

SN - 3540654739

SN - 9783540654735

T3 - Lecture Notes in Computer Science

SP - 288

EP - 301

BT - Graph Drawing - 6th International Symposium, GD 1998, Proceedings

A2 - Whitesides, Sue H.

PB - Springer

T2 - Graph Drawing 1998

Y2 - 13 August 1998 through 15 August 1998

ER -

NP-completeness of some tree-clustering problems

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this