1984 Reports
An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs
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
- cucs-100-84.pdf application/pdf 813 KB Download File
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