Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

F. Bock, An algorithm to construct a minimum directed spanning tree in a directed network, in:Developments in Operations Research, Gordon and Breach, New York, 1971, 29–44.

O. Boruvka, O jistem problemu minimálni’mPráca Moravské Priŕodovědecké Spolěcnosti 3 (1926), 37–58. (In Czech).

P. M. Camerini, L. Fratta andF. Maffioli, A note on finding optimum branchings,Networks 9 (1979), 309–312.

D. Cheriton andR. E. Tarjan, Finding minimum spanning trees,SIAM J. Comput. 5 (1976), 724–742.

Y. J. Chu andT. H. Liu, On the shortest arborescence of a directed graph,Sci. Sinica 14 (1965), 1396–1400.

J. Edmonds, Optimum branchings,J. Res. Nat. Bur. Standards 71B (1967), 233–240.

M. L. Fredman andR. E. Tarjan, Fibonacci heaps and their uses in network optimization algorithms,J. Assoc. Comput. Mach., to appear; also Proc. 25 th Annual IEEE Symp. on Found. of Comp. Sci. (1984), 338–346.

H. N. Gabow, Z. Galil andT. H. Spencer, Efficient implementation of graph algorithms using contraction,Proc. 25 th Annual IEEE Symp. on Found. of Comp. Sci. (1984), 347–357.

H. N. Gabow, Z. Galil andT. Spencer, Efficient implementation of graph algorithms using contraction,J. Assoc. Comput. Mach., submitted.

H. N. Gabow andR. E. Tarjan, Efficient algorithms for a family of matroid intersection problems,J. Algorithms 5 (1984), 80–131.

R. L. Graham andP. Hell, On the history of the minimum spanning tree problem,Ann. History of Computing 7 (1985), 43–57.

R. M. Karp, A simple derivation of Edmonds’ algorithm for optimum branchings,Networks 1 (1971), 265–272.

J. Komlós, Linear verification for spanning trees,Combinatorica 5 (1985), 57–65.

R. E. Tarjan, Efficiency of a good but not linear set union algorithm,J. Assoc. Comput. Mach. 22 (1975), 215–225.

R. E. Tarjan, Finding optimum branchings,Networks 7 (1977), 25–35.

R. E. Tarjan, Applications of path compression on balanced trees,J. Assoc. Comput. Mach. 26 (1979), 690–715.

R. E. Tarjan,Data Structures and Network Algorithms, CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.

R. E. Tarjan andJ. Van Leeuwen, Worst-case analysis of set union algorithms,J. Assoc. Comput. Mach. 31 (1984), 245–281.

R. E. Tarjan, Amortized computational complexity,SIAM J. Alg. Disc. Meth. 6 (1985), 306–318.

A. Yao, AnO(|E|log log|V|) algorithm for finding minimum spanning trees,Inform. Process. Lett. 4 (1975), 21–23.