Finding Edge-disjoint paths in partial k-trees

Xiao Zhou, Syurei Tamura, Takao Nishizeki

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)


For a given graph G and p pairs (Si, Ti), 1 ≤ i ≤ p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths Pi, 1 ≤ i ≤ p, connecting Si and Ti. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of tree width bounded by a fixed integer k), but it has not been-known whether the edge-disjoint paths problem can be solved in polynomial time for partial k-trees unless p = O(1). This paper gives two algorithms for the edge-disjoint paths problem on partial k-trees. The first one solves the problem for any partial k-tree G and runs in polynomial time if p = O(log n) and in linear time if p = O(1), where n is the number of vertices in G. The second one solves the problem under some restriction on the location of terminal pairs even if p > log n.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings
EditorsTetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano, Subhash Suri
PublisherSpringer Verlag
Number of pages10
ISBN (Print)3540620486, 9783540620488
Publication statusPublished - 1996
Event7th International Symposium on Algorithms and Computation, ISAAC 1996 - Osaka, Japan
Duration: 1996 Dec 161996 Dec 18

Publication series

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


Conference7th International Symposium on Algorithms and Computation, ISAAC 1996


  • Bounded tree-width
  • Edge-coloring
  • Edge-disjoint paths
  • Partial k-tree
  • Polynomial-time algorithm


Dive into the research topics of 'Finding Edge-disjoint paths in partial k-trees'. Together they form a unique fingerprint.

Cite this