Linear Verification for Spanning Trees

Given a rooted tree with values associated with the n vertices and a set A of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only 5n + n log [(|A|+n)/n] comparisons. This leads to a spanning tree verification algorithm using O(n+e) comparisons in a graph with n vertices and e edges. No implementation is offered.

Authors

• János Komlós

Keywords

• Tree graphs
• Costs
• Circuit testing
• Sorting
• Spanning Tree
• Binary Tree
• Undirected Network