Linear verification for spanning trees

DOI10.1007/BF02579443MaRDI QIDQ1066909zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• An inverse-Ackermann type lower bound for online minimum spanning tree verification
• A simpler minimum spanning tree verification algorithm
• 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
• Finding Minimum Spanning Trees
• Information Bounds Are Weak in the Shortest Distance Problem

Cited in

(15)

• Polynomial testing of the query Is \(a^ b\geq c^ d?\) with application to finding a minimal cost reliability ratio spanning tree
• scientific article; zbMATH DE number 1264417 (Why is no real title available?)
• Succinct indices for path minimum, with applications
• Distributed verification of minimum spanning trees
• An optimal EREW PRAM algorithm for minimum spanning tree verification
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• scientific article; zbMATH DE number 4139518 (Why is no real title available?)
• scientific article; zbMATH DE number 496232 (Why is no real title available?)
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The saga of minimum spanning trees
• A simpler minimum spanning tree verification algorithm
• A simpler minimum spanning tree verification algorithm
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• The algebraic Monge property and path problems
• On Cartesian trees and range minimum queries

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1066909)