About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.