DocumentCode :
3174330
Title :
Sublinear-time parallel algorithms for matching and related problems
Author :
Goldberg, Andrew V. ; Plotkin, Serge A. ; Vaidya, Pravin M.
Author_Institution :
Dept. of Comput. Sci., Stanford Univ., CA, USA
fYear :
1988
fDate :
24-26 Oct 1988
Firstpage :
174
Lastpage :
185
Abstract :
The authors present the first sub-linear-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. The results are based on a better understanding of the combinatorial structure of the above problems, which lead to new algorithmic techniques. In particular, it is shown 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. It is also shown how to apply the techniques to design parallel algorithms for the weighted versions of the above problems
Keywords :
parallel algorithms; combinatorial structure; depth-first search; matching; maximal node-disjoint paths; node-disjoint paths; sublinear-time parallel algorithms; zero-one networks; Algorithm design and analysis; Computer networks; Computer science; Concurrent computing; Contracts; Costs; Laboratories; Parallel algorithms; Parallel processing; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1988., 29th Annual Symposium on
Conference_Location :
White Plains, NY
Print_ISBN :
0-8186-0877-3
Type :
conf
DOI :
10.1109/SFCS.1988.21935
Filename :
21935
Link To Document :
بازگشت