TY - RPRT
T1 - Lower Bounds for Labeling Schemes Supporting Ancestor, Sibling, and Connectivity Queries
AU - Alstrup, Stephen
AU - Rauhe, Theis
PY - 2001/12
Y1 - 2001/12
N2 - 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) .
AB - 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) .
KW - Labeling scheme
KW - Ancestor relation
KW - Binary string
KW - Tree structures
KW - Connectivity queries
M3 - Report
T3 - IT University Technical Report Series
BT - Lower Bounds for Labeling Schemes Supporting Ancestor, Sibling, and Connectivity Queries
PB - IT-Universitetet i København
CY - Copenhagen
ER -