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 (12)

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

This page was built for publication: Linear verification for spanning trees