The Maximum Weight Perfect Matching Problem for Complete Weighted Graphs is in PC
Auteur : Constantine Nyemasem Komla Osiakwan, Selim G. Akl
Date de publication : 1990
Éditeur : Queen's University of Kingston. Department of Computing and Information Science
Nombre de pages : 40
Résumé du livre
Abstract: "A matching M of a graph G = (V, E) is a subset of the set of edges E such that no two edges in M are adjacent. A maximum weight (perfect) matching of a (complete) weighted graph is a (perfect) matching of the graph where the sum of the weights of the edges in the matching is maximum. There are efficient sequential algorithms that use linear programming (LP) for computing maximum weight matchings. These are primal-dual algorithms and have time complexity of O(n3). A number of randomized parallel algorithms for maximum weight matchings have also appeared in the literature. Finding a deterministic parallel algorithm for computing maximum weight matchings in non-bipartite graphs has been an open problem for some time