Linear verification for spanning trees

DOI10.1007/BF02579443zbMath0579.05031OpenAlexW2152506249MaRDI QIDQ1066909

János Komlós

Publication date: 1985

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579443

zbMATH Keywords

verificationalgorithmspanning treenumber of comparisons

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Designs and configurations (05B99)

Related Items

Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Succinct indices for path minimum, with applications, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, An optimal EREW PRAM algorithm for minimum spanning tree verification, A simpler minimum spanning tree verification algorithm, Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems, Tight bounds for distributed minimum-weight spanning tree verification, Distributed verification of minimum spanning trees, The saga of minimum spanning trees, On Cartesian trees and range minimum queries, The algebraic Monge property and path problems, A simpler minimum spanning tree verification algorithm

Cites Work

• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Applications of Path Compression on Balanced Trees
• Information Bounds Are Weak in the Shortest Distance Problem
• Finding Minimum Spanning Trees