@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",

}