Academic Commons


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
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.