Abstract
The problem considered here is that of determining whether a given spanning tree is a minimal spanning tree. In 1984 Komlós presented an algorithm which required only a linear number of comparisons, but nonlinear overhead to determine which comparisons to make. We simplify his algorithm and give a linear-time procedure for its implementation in the unit cost RAM model. The procedure uses table lookup of a few simple functions, which we precompute in time linear in the size of the tree.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
B. Dixon, M. Rauch, and R. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time,SIAM J. Comput.,21(6) (1992), 1184–1192.
D. Harel and R. E. Tarjan, Fast algorithms for finding nearest common ancestors,SIAM J. Comput.,13 (1984), 338–355.
D. Karger, P. N. Klein, and R. E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees,J. Assoc. Comput. Mach.,42 (1995), 321–328.
J. Komlós, Linear verification for spanning trees,Combinatorica,5 (1985), 57–65.
B. Schieber and U. Vishkin, On finding lowest common ancestors: simplification and parallelization,SIAM J. Comput.,17 (1988), 1253–1262.
R. Tarjan, Applications of path compressions on balanced trees,J. Assoc. Comput. Mach.,26 (1979), 690–715.
R. Tarjan,Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 44, SIAM, Philadelphia, PA, 1983, p. 73.
Author information
Authors and Affiliations
Additional information
Communicated by Ming Y. Kao.
Rights and permissions
About this article
Cite this article
King, V. A simpler minimum spanning tree verification algorithm. Algorithmica 18, 263–270 (1997). https://doi.org/10.1007/BF02526037
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02526037