An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

Galil, Zvi; Micali, Silvio; Gabow, Harold

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O (log n) time. We use these generalized priority queues to construct an O (EV log V) algorithm for finding a maximal weighted matching in general graphs.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-100-84
Published Here
February 10, 2012