Sublinear-Time Parallel Algorithms for Matching and Related Problems
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 dining 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1988
- Accession Number
- ADA197411
Entities
People
- Andrew V. Goldberg
- Pravin Vaidya
- Serge A. Plotkin
Organizations
- Massachusetts Institute of Technology