Finding edge-disjoint paths in partial k-trees

For a given graph G and p pairs (s(i), t(i)), 1 less than or equal to i les s than or equal to p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P-i, 1 less than or equal to i less than or equal to p, connecting s(i) and t(i). Many combinatorial problems c an be efficiently solved for partial k-trees (graphs of treewidth bounded b y a fixed integer k), but the edge-disjoint paths problem is NP-complete ev en for partial 3-trees. This paper gives two algorithms for the edge-disjoi nt paths problem on partial k-trees. The first one serves the problem for a ny partial k-tree G and runs in polynomial time if p = O(log n) and in line ar 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 pair s even if p greater than or equal to log n.