BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-88-1211
       ENTRY:: April 24, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Sublinear-Time Parallel Algorithms
        TYPE:: Technical Report
      AUTHOR:: Goldberg, A. V.
      AUTHOR:: Plotkin, S. A.
      AUTHOR:: Vaidya, P. M.
        DATE:: June 1988
       PAGES:: 30
    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.
       NOTES:: [Adminitrivia V1/Prg/19950424]
         END:: STAN//CS-TR-88-1211