Reports

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.

Subjects

Files

More About This Work

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