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
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