Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs
- 1 November 1982
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 255-261
- https://doi.org/10.1109/sfcs.1982.36
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.Keywords
This publication has 2 references indexed in Scilit:
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965