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

Abstract

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.