The edge-disjoint paths problem is np-complete for partial k-trees

Xiao Zhou; Takao Nishizeki

doi:10.1007/3-540-49381-6_44

The edge-disjoint paths problem is np-complete for partial k-trees

Xiao Zhou, Takao Nishizeki

INF - System Information Sciences

Tohoku University

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

7 Citations (Scopus)

Abstract

Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial k-trees (graphs of treewidth bounded by a constant k) and can be efficiently solved in polynomial time or mostly in linear time for partial k-trees. On the other hand, very few problems are known to be NP-complete for partial k-trees with bounded k. These include the subgraph isomorphism problem and the bandwidth problem. However, all these problems are NP-complete even for ordinary trees or forests. In this paper we show that the edge-disjoint paths problem is NP-complete for partial k-trees with some bounded k, say k = 3, although the problem is trivially solvable for trees.

Original language	English
Title of host publication	Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings
Publisher	Springer Verlag
Pages	417-426
Number of pages	10
ISBN (Print)	3540653856, 9783540653851
DOIs	https://doi.org/10.1007/3-540-49381-6_44
Publication status	Published - 1998
Event	9th Annual International Symposium on Algorithms and Computation, ISAAC'98 - Taejon, Korea, Republic of Duration: 1998 Dec 14 → 1998 Dec 16

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1533 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th Annual International Symposium on Algorithms and Computation, ISAAC'98
Country/Territory	Korea, Republic of
City	Taejon
Period	98/12/14 → 98/12/16

Access to Document

10.1007/3-540-49381-6_44

Cite this

Zhou, X., & Nishizeki, T. (1998). The edge-disjoint paths problem is np-complete for partial k-trees. In Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings (pp. 417-426). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1533 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-49381-6_44

@inproceedings{a50a3b1a92bd41c5b58d1f30958d604d,

title = "The edge-disjoint paths problem is np-complete for partial k-trees",

abstract = "Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial k-trees (graphs of treewidth bounded by a constant k) and can be efficiently solved in polynomial time or mostly in linear time for partial k-trees. On the other hand, very few problems are known to be NP-complete for partial k-trees with bounded k. These include the subgraph isomorphism problem and the bandwidth problem. However, all these problems are NP-complete even for ordinary trees or forests. In this paper we show that the edge-disjoint paths problem is NP-complete for partial k-trees with some bounded k, say k = 3, although the problem is trivially solvable for trees.",

author = "Xiao Zhou and Takao Nishizeki",

year = "1998",

doi = "10.1007/3-540-49381-6_44",

language = "English",

isbn = "3540653856",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "417--426",

booktitle = "Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings",

address = "Germany",

note = "9th Annual International Symposium on Algorithms and Computation, ISAAC'98 ; Conference date: 14-12-1998 Through 16-12-1998",

}

Zhou, X & Nishizeki, T 1998, The edge-disjoint paths problem is np-complete for partial k-trees. in Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1533 LNCS, Springer Verlag, pp. 417-426, 9th Annual International Symposium on Algorithms and Computation, ISAAC'98, Taejon, Korea, Republic of, 98/12/14. https://doi.org/10.1007/3-540-49381-6_44

The edge-disjoint paths problem is np-complete for partial k-trees. / Zhou, Xiao; Nishizeki, Takao.
Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Springer Verlag, 1998. p. 417-426 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1533 LNCS).

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

TY - GEN

T1 - The edge-disjoint paths problem is np-complete for partial k-trees

AU - Zhou, Xiao

AU - Nishizeki, Takao

PY - 1998

Y1 - 1998

N2 - Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial k-trees (graphs of treewidth bounded by a constant k) and can be efficiently solved in polynomial time or mostly in linear time for partial k-trees. On the other hand, very few problems are known to be NP-complete for partial k-trees with bounded k. These include the subgraph isomorphism problem and the bandwidth problem. However, all these problems are NP-complete even for ordinary trees or forests. In this paper we show that the edge-disjoint paths problem is NP-complete for partial k-trees with some bounded k, say k = 3, although the problem is trivially solvable for trees.

AB - Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial k-trees (graphs of treewidth bounded by a constant k) and can be efficiently solved in polynomial time or mostly in linear time for partial k-trees. On the other hand, very few problems are known to be NP-complete for partial k-trees with bounded k. These include the subgraph isomorphism problem and the bandwidth problem. However, all these problems are NP-complete even for ordinary trees or forests. In this paper we show that the edge-disjoint paths problem is NP-complete for partial k-trees with some bounded k, say k = 3, although the problem is trivially solvable for trees.

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

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

U2 - 10.1007/3-540-49381-6_44

DO - 10.1007/3-540-49381-6_44

M3 - Conference contribution

AN - SCOPUS:84867453493

SN - 3540653856

SN - 9783540653851

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 417

EP - 426

BT - Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings

PB - Springer Verlag

T2 - 9th Annual International Symposium on Algorithms and Computation, ISAAC'98

Y2 - 14 December 1998 through 16 December 1998

ER -

Zhou X, Nishizeki T. The edge-disjoint paths problem is np-complete for partial k-trees. In Algorithms and Computation - 9th International Symposium, ISAAC'98, Proceedings. Springer Verlag. 1998. p. 417-426. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-49381-6_44

The edge-disjoint paths problem is np-complete for partial k-trees

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this