Report Number: CS-TR-88-1211
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