Technical Report 396-1994

Title

A Practical Linear Time Algorithm for Disjoint Paths in Graphs with Bounded Tree-width

Author

Petra Scheffler

Source

Download as [ps.gz]

Classification

not available

Keywords

not available

Abstract

A linear time algorithm is presented that finds disjoint paths between given pairs of vertices in an undirected graph with tree-width bounded by a constant. The number of paths is {bf not} assumed to be fixed.