Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs
Zvi Galil, Silvio Micali, Harold N. Gabow · 1982
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.