2011/12/05 by Mark Heiligman, Heiligman, Mark
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #cs.DS #quant-ph
paper · pdf · doi:10.48550/arxiv.1112.1139
5 papges
arxiv created 2011/12/05 · openalex publication_date 2011/12/05 · arxiv updated 2011/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Previous studies has shown that for a weighted undirected graph having n vertices and m edges, a minimal weight spanning tree can be found with O^*(√(mn)) calls to the weight oracle. The present note shows that a given spanning tree can be verified to be a minimal weight spanning tree with only O(n) calls to the weight oracle and O(n+√(m)log n) total work.