@inproceedings{8ad260e6ff9c447d82c58be46f12c945,
title = "Linear verification for spanning trees",
abstract = "Given a rooted tree with values associated with the n vertices and a set A of directed paths (queries), we describe an algorithm which finds the maximum value of every one of the given paths, and which uses only {equation presented} comparisons. This leads to a spanning tree verification algorithm using O(n + e) comparisons in a graph with n vertices and e edges. No implementation is offered. ",
author = "J{\'a}nos Koml{\'o}s",
note = "Publisher Copyright: {\textcopyright} 1984 IEEE.; 25th Annual Symposium on Foundations of Computer Science, FOCS 1984 ; Conference date: 24-10-1984 Through 26-10-1984",
year = "1984",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "201--206",
booktitle = "25th Annual Symposium on Foundations of Computer Science, FOCS 1984",
address = "United States",
}