An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm

Abstract

Goldberg, Plotkin, and Vaidya recently developed a sublinear-time parallel algorithm for finding maximal node-disjoint paths [3] with the concurrent-read concurrent-write random access machine model (CRCW PRAM) [2] by balancing two approaches to the problem appropriately. We improve their results by finding a better balance factor. Our results are as follows: we can find maximal node-disjoint paths for undirected graphs in O(√nlog2n) time with O(n + m) processors improved from O(√nlog3n) time with the same number of processors; for directed graphs in O(√nlog5/2n) time with BFS(n, m)processors improved from O(√nlog3n) time with the same number of processors. Here BFS(n, m) denotes the maximum of n + m and the number of processors required to find a breadth-first search tree in O(log2n) time for a directed graph with n vertices and m edges. As a consequence of our result, we show that a depth-first search tree in an undirected graph can be found in O(√nlog5n) time with O(n + m) processors. © 1989.