Title :
The maximum weight perfect matching problem for complete weighted graphs is in PC
Author :
Osiakwan, C.N.K. ; Akl, S.G.
Author_Institution :
Dept. of Comput. & Inf. Sci., Queen´´s Univ., Kingston, Ont., Canada
Abstract :
There are efficient sequential algorithms that use linear programming (LP) for computing maximum weight matchings. Finding a deterministic parallel algorithm for computing maximum weight matchings in complete graphs has been an open problem for some time. Since LP is known to be P-complete, then, by the parallel computation thesis, it is unlikely that there exists an NC algorithm that uses LP to solve the maximum weight matching problem. The authors present an LP-based parallel algorithm for maximum weight matching in a complete weighted graph. The algorithm is designed for the EREW PRAM model of parallel computation, and runs in O(n3/p+n2logn) time for p⩽n, where p is the number of processors and n is the number of vertices in the graph. This algorithm provides an optimal speedup with respect to the O(n 3) sequential LP-based solution of Gabow (1974) or Lawler (1976), for p⩽n/log n. This is the first deterministic optimal speedup parallel algorithm designed for the maximum weight matching problem on complete graphs
Keywords :
graph theory; parallel algorithms; search problems; EREW PRAM model; complete weighted graph; deterministic parallel algorithm; linear programming; maximum weight matchings; optimal speedup; parallel computation; sequential algorithms; Algorithm design and analysis; Computational modeling; Concurrent computing; Councils; Information science; Joining processes; Linear programming; Parallel algorithms; Phase change random access memory; Polynomials;
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
DOI :
10.1109/SPDP.1990.143503