Linear verification for spanning trees (Q1066909): Difference between revisions

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.