Abstract
This paper is composed of two parts. In the first part, an improved algorithm is presented for the problem of finding length-bounded two vertex-disjoint paths in an undirected planar graph. The presented algorithm requires O(n 3 bmin) time and O(n 2 bmin) space, where bmin is the smaller of the two given length bounds. In the second part of this paper, we consider the minmax k vertex-disjoint paths problem on a directed acyclic graph, where k ≥ 2 is a constant. An improved algorithm and a faster approximation scheme are presented. The presented algorithm requires O(n k+1 M k - 1 ) time and O(nkM k - 1 ) space, and the presented approximation scheme requires O((1/ε) k - 1 n 2k log k - 1 M) time and O((1/ε) k - 1 n2 k - 1 log k - 1 M) space, where ε is the given approximation parameter and M is the length of the longest path in an optimal solution. © 2010 Elsevier Inc. All rights reserved.