An inverse-Ackermann type lower bound for online minimum spanning tree verification

DOI10.1007/s00493-006-0014-1zbMath1121.05067OpenAlexW2042125957MaRDI QIDQ858114

Seth Pettie

Publication date: 8 January 2007

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-006-0014-1

zbMATH Keywords

minimum spanning tree verification

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Succinct indices for path minimum, with applications ⋮ Shortest beer path queries in outerplanar graphs ⋮ The saga of minimum spanning trees ⋮ A new algorithm for the minimum spanning tree verification problem

This page was built for publication: An inverse-Ackermann type lower bound for online minimum spanning tree verification