Identifying Nearest Common Ancestors in a Distributed Environment

Stephen Alstrup, Theis Rauhe, Cyril Gavoille, Haim Kaplan

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

Abstract

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.
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2001-6
Antal sider14
ISBN (Elektronisk)87-7949-008-5
StatusUdgivet - aug. 2001
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2001-6
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Identifying Nearest Common Ancestors in a Distributed Environment'. Sammen danner de et unikt fingeraftryk.

Citationsformater