Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph |
| |
Authors: | Chih-Chiang Yu Chien-Hsin Lin Biing-Feng Wang |
| |
Affiliation: | Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 30013, ROC |
| |
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(n3bmin) time and O(n2bmin) 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(nk+1Mk−1) time and O(nkMk−1) space, and the presented approximation scheme requires O((1/?)k−1n2klogk−1M) time and O((1/?)k−1n2k−1logk−1M) space, where ? is the given approximation parameter and M is the length of the longest path in an optimal solution. |
| |
Keywords: | Algorithms Directed acyclic graphs Dynamic programming Fully polynomial-time approximation schemes Planar graphs Pseudo-polynomial time Vertex-disjoint paths |
本文献已被 ScienceDirect 等数据库收录! |
|