Comparative studies of priority queue implementation in minimum spanning tree algorithms

Date

1983

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

The minimum spanning tree algorithms have important applications in the construction of shortest connection networks. The most important part of the minimum spanning tree algorithms that determines their time complexity is the manipulation of priority queues. Cheriton & Tarjan proposed a refined leftist tree data structure for implementing priority queues and achieved a worst-case time bound of m log log n for the minimum spanning tree problem. Vuillemin then discovered a new data structure, the binomial queue, which was proved better than the leftist tree for the implemention of priority queues. We investigate the average-case time complexity of minimum spanning tree algorithms based on several different implementations of priority queues. Experiments on large-size random graphs are performed to compare the results with the theoretical analysis. In general, our findings agree with the theoretical analysis.

Description

Keywords

Trees (Graph theory), Queuing theory, Algorithms

Citation