Institution: Stanford University, Department of Computer Science

Title: Sublinear-Time Parallel Algorithms

Author: Goldberg, A. V.

Author: Plotkin, S. A.

Author: Vaidya, P. M.

Date: June 1988

Abstract: This paper presents the first sublinear-time deterministic parallel algorithms for bipartite matching and several related problems, including maximal node-disjoint paths, depth-first search, and flows in zero-one networks. Our results are based on a better understanding of the combinatorial structure of the above problems, which leads to new algorithmic techniques. In particular, we show how to use maximal matching to extend, in parallel, a current set of node-disjoint paths and how to take advantage of the parallelism that arises when a large number of nodes are "active" during an execution of a push/relabel network flow algorithm. We also show how to apply our techniques to design parallel algorithms for the weighted versions of the above problems. In particular, we present sublinear-time deterministic parallel algorithms for finding a minimum-weight bipartite matching and for finding a minimum-cost flow in a network with zero-one capacities, if the weights are polynomially bounded integers.

http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1211/CS-TR-88-1211.pdf