Identifying Nearest Common Ancestors in a Distributed Environment
- Stephen Alstrup,
- Theis Rauhe,
- Cyril Gavoille,
- Haim Kaplan
- University of Bordeaux,
- Tel Aviv University
Research Output:
Book / Anthology / Report
Report
Open access
Publication Information
Output type
Research Output:
Book / Anthology / Report
Report
Original language
EnglishPublication milestones
- Published - 08/2001
Publication status
Published - 08/2001
Place of publication
CopenhagenEdition
TR-2001-6Publisher
IT-Universitetet i København, DenmarkBook series
- Book series name: IT University Technical Report Series
Series number: TR-2001-6
ISSN: 1600-6100
ISBN (Electronic)
87-7949-008-5Abstract
We give a simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels assigned by out algorithm are of size O(log n) bits where n is the number of nodes on the tree. The algorithm runs in O(n) time.
Access to documents
Final published version, 233.93 KB