Finding edge-disjoint paths in partial \(k\)-trees
For a given graph \(G\) and \(p\) pairs \((s_i,t_i)\), \(1\leq i\leq p\), of vertices of \(G\), the edge-disjoint paths problem is to find \(p\) pairwise edge-disjoint paths \(P_i\), \(1\leq i \leq p\), connecting \(s_i\) and \(t_i\). 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 restrictions on the location of terminal pairs even if \(p\geq \log n\).
scientific article; zbMATH DE number 1417529