\input zb-basic
\input zb-ioport
\iteman{io-port 00166206}
\itemau{Goldberg, Andrew V.; Plotkin, Serge A.; Vaidya, Pravin M.}
\itemti{Sublinear-time parallel algorithms for matching and related problems.}
\itemso{J. Algorithms 14, No.2, 180-213 (1993).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{sublinear-time deterministic parallel algorithms; bipartite matching; maximal node-disjoint paths; depth-first search; flows in zero-one networks; minimum-cost flow}
\itemli{doi:10.1006/jagm.1993.1009}
\end