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

Zvi Galil, Silvio Micali, Harold N. Gabow

SIAM Journal on Computing · 1986 · 131 citations · 4 references

DOIFull text

Open access

Concepts

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.

References

4