We present a labeling scheme for rooted trees that support ancestor queries. Given a tree, the scheme assigns to each node a label which is a binary string. Given the labels of any two nodes u and v, it can in constant time be determined whether u is ancestor to v alone from these labels. For trees size of n our scheme assigns labels of size bounded by log n + O (√log n) bits to each node. This improves a recent result of a biteboul, Kaplan and Milo at SODA'01, where a labeling scheme with labels of size 3/2 log n + O(loglog n) was presented. The problem is among other things motivated in connection with efficient representation of information for XML-based research engines for the internet.
Udgivelsessted | Copenhagen |
---|
Forlag | IT-Universitetet i København |
---|
Udgave | TR-2001-5 |
---|
Antal sider | 12 |
---|
ISBN (Elektronisk) | 87-7949-009-3 |
---|
Status | Udgivet - jul. 2001 |
---|
Udgivet eksternt | Ja |
---|
Navn | IT University Technical Report Series |
---|
Nummer | TR-2001-5 |
---|
ISSN | 1600-6100 |
---|