Improved processor bounds for combinatorial problems in RNC |
| |
| Authors: | Z. Galil V. Pan |
| |
| Affiliation: | (1) Computer Science Department, Columbia University, USA;(2) Tel-Aviv University, Israel;(3) Computer Science Department, State University of New York at Albany, USA |
| |
| Abstract: | Our main result improves the known processor bound by a factor ofn4 (maintaining the expected parallel running time,O(log3n)) for the following important problem:find a perfect matching in a general or in a bipartite graph with n vertices. A solution to that problem is used in parallel algorithms for several combinatorial problems, in particular for the problems of finding i) a (perfect) matching of maximum weight, ii) a maximum cardinality matching, iii) a matching of maximum vertex weight, iv) a maximums-t flow in a digraph with unit edge capacities. Consequently the known algorithms for those problems are substantially improved.The results of this paper have been presented at the 26-th Annual IEEE Symp. FOCS, Portland, Oregon (October 1985).Partially supported by NSF Grants MCS 8303139 and DCR 8511713.Supporeted by NSF Grants MCS 8203232 and DCR 8507573. |
| |
| Keywords: | 05 C 68 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
