Lower Bounds for Labeling Schemes Supporting Ancestor, Sibling, and Connectivity Queries

Stephen Alstrup, Theis Rauhe

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

Abstract

Given a tree, a labeling scheme assigns a label, which is a binary string, to each node. Given the labels of any two nodes u  and v, it can be determined, if a certain property holds u for and v, alone from these labels.
For trees of size n, we show that any labeling scheme for testing ancestor relation uses labels of size log n+Ω(loglog n) to the nodes. If the labels has to distinguish the nodes, i.e., the label of a node is unique, we testing for sibling requires labels of size log n+(-)(loglog d)  for trees with degree , and connectivity queries for forests requires labels of size log n+(-)(loglog n) .
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2001-10
Antal sider9
ISBN (Elektronisk)87-7949-013-1
StatusUdgivet - dec. 2001
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2001-10
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Lower Bounds for Labeling Schemes Supporting Ancestor, Sibling, and Connectivity Queries'. Sammen danner de et unikt fingeraftryk.

Citationsformater