Abstract
Given a rooted tree with values associated with then vertices and a setA of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only
comparisons.
This leads to a spanning tree verification algorithm usingO(n+e) comparisons in a graph withn vertices ande edges.
No implementation is offered.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D. Cheriton andR. E. Tarjan, Finding Minimum Spanning Trees,SIAM J. on Computing,5 (1976), 724–742.
M. Fredman andR. E. Tarjan,private communication, December 1983.
R. L. Graham, A. C. Yao, andF. F. Yao, Information Bounds are Weak in the Shortest Distance Problem,JACM,27 (1980), 428- 444.
D. Harel, A Linear Time Algorithm for the Lowest Common Ancestors Problem,Proc. 21st Annual Symp. on Foundations of Computer Science, (1980), 308–319.
R. E. Tarjan, Application of Path Compression on Balanced Trees,JACM,26 (1979), 690–715.
A. C. Yao, AnO(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees,Information Processing Letters,4 (1975), 21–23.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Komlós, J. Linear verification for spanning trees. Combinatorica 5, 57–65 (1985). https://doi.org/10.1007/BF02579443
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02579443