## Abstract

For a given graph G and p pairs (s_{i}, t_{i}), 1 ≤ i ≤ p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P_{i}, 1 ≤ i ≤ p, connecting s_{i} and t_{i}. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but the edge-disjoint paths problem is NP-complete even for partial 3-trees. 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 language | English |
---|---|

Pages (from-to) | 3-30 |

Number of pages | 28 |

Journal | Algorithmica |

Volume | 26 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2000 |

## Keywords

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