# zbMATH — the first resource for mathematics

Linear verification for spanning trees. (English) Zbl 0579.05031
The paper deals with the following special problem: (Q) Given an n- element set $$E=(e_ 1,...,e_ n)$$, and a list of m subsets of $$\{$$ 1,...,n$$\}$$, $$L=(S_ 1,...,S_ m)$$. Find the maxima $$M_ i=\max_{j\in S_ i}e_ j,$$ $$i=1,...,m$$. For the solution of the problem an algorithm is proposed which finds all maxima in linear time when only the total number of comparisons is taken into account.
Let G be a finite undirected graph and T a spanning tree of G. For any edge $$x\in G-T$$ denote $$C_ x$$ the circuit created by x and edges from T. Considering E being the set of weighted edges of G and $$L=\{C_ x: x\in G\setminus T\}$$ the problem (Q) is converted into the problem of verification whether the given spanning tree T is of minimum weight or not. The result is rather of theoretical value since no implementation of the method is offered.
Reviewer: R.Jiroušek

##### MSC:
 05C35 Extremal problems in graph theory 05C05 Trees 05B99 Designs and configurations
##### Keywords:
algorithm; number of comparisons; verification; spanning tree
Full Text:
##### References:
 [1] D. Cheriton andR. E. Tarjan, Finding Minimum Spanning Trees,SIAM J. on Computing,5 (1976), 724–742. · Zbl 0358.90069 · doi:10.1137/0205051 [2] M. Fredman andR. E. Tarjan,private communication, December 1983. [3] R. L. Graham, A. C. Yao, andF. F. Yao, Information Bounds are Weak in the Shortest Distance Problem,JACM,27 (1980), 428- 444. · Zbl 0475.68043 · doi:10.1145/322203.322206 [4] D. Harel, A Linear Time Algorithm for the Lowest Common Ancestors Problem,Proc. 21st Annual Symp. on Foundations of Computer Science, (1980), 308–319. [5] R. E. Tarjan, Application of Path Compression on Balanced Trees,JACM,26 (1979), 690–715. · Zbl 0413.68063 · doi:10.1145/322154.322161 [6] A. C. Yao, AnO(|E| log log |V|) Algorithm for Finding Minimum Spanning Trees,Information Processing Letters,4 (1975), 21–23. · Zbl 0307.68028 · doi:10.1016/0020-0190(75)90056-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.