@inproceedings{7f247e1301154b7dbbe9ffe868c7fcd4,

title = "Finding Edge-disjoint paths in partial k-trees",

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

keywords = "Bounded tree-width, Edge-coloring, Edge-disjoint paths, Partial k-tree, Polynomial-time algorithm",

author = "Xiao Zhou and Syurei Tamura and Takao Nishizeki",

note = "Publisher Copyright: {\textcopyright} 1996 Springer-Verlag. All rights reserved.; 7th International Symposium on Algorithms and Computation, ISAAC 1996 ; Conference date: 16-12-1996 Through 18-12-1996",

year = "1996",

doi = "10.1007/bfb0009496",

language = "English",

isbn = "3540620486",

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

publisher = "Springer Verlag",

pages = "203--212",

editor = "Tetsuo Asano and Yoshihide Igarashi and Hiroshi Nagamochi and Satoru Miyano and Subhash Suri",

booktitle = "Algorithms and Computation - 7th International Symposium, ISAAC 1996, Proceedings",

address = "Germany",

}