Finding edge-disjoint paths in partial \(k\)-trees (Q1969940): Difference between revisions

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\).