SIAM Journal on Computing · 1986 · 131 citations · 4 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationGraph AlgorithmsMatching TheoryPriority QueuesQueueing SystemsQueueing TheoryGraph MatchingMatching AlgorithmsMatching ProblemsPriority Queue Implementation
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.
4
Jack Edmonds · Canadian Journal of Mathematics · 1965 · 2.4K citations · Full text
Robert E. Tarjan · Networks · 1977 · 371 citations