Trans-dichotomous algorithms for minimum spanning trees and shortest paths

Ahuja, 1990, Faster algorithms for the shortest path problem, J. Assoc. Comput. Mach., 37, 213, 10.1145/77600.77615

Ajtai, 1984, Hash functions for priority queues, Inform. and Comput., 63, 217

Ben-Or, 1983, Lower bounds for algebraic computation trees, 80

B. Dixon, M. Rauch, and R. E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, unpublished manuscript.

Driscoll, 1988, An alternative to Fibonacci heaps with applications to parallel computation, Comm. ACM, 31, 1343, 10.1145/50087.50096

Fredman, 1987, Fibonacci heaps and their uses in improved network optimization algorithms, J. Assoc. Comput. Mach., 34, 596, 10.1145/28869.28874

Fredman, 1993, Surpassing the information theoretic bound with fusion trees, J. Comput. System Sci., 47, 10.1016/0022-0000(93)90040-4

Gabow, 1986, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica, 6, 109, 10.1007/BF02579168

Komlos, 1984, Linear verification for spanning trees, 201

Peterson, 1987, A Balanced Tree Scheme for Meldable Heaps with Updates

Tarjan, 1983

Van Emde Boas, 1977, Design and implementation of an efficient priority queue, Math. Systems Theory, 10, 99, 10.1007/BF01683268