Linear verification for spanning trees (Q1066909): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: János Komlós / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Radim Jiroušek / rank | |||
Normal rank |
Revision as of 12:00, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear verification for spanning trees |
scientific article |
Statements
Linear verification for spanning trees (English)
0 references
1985
0 references
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.
0 references
algorithm
0 references
number of comparisons
0 references
verification
0 references
spanning tree
0 references