Average case analysis for tree labelling schemes

Ming-Yang Kao, Xiang Yang Li*, Weizhao Wang

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least frac(1, 8) log2 n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ (log n {dot operator} log (Hn (T))), where Hn (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.

Original languageEnglish (US)
Pages (from-to)271-291
Number of pages21
JournalTheoretical Computer Science
Volume378
Issue number3
DOIs
StatePublished - Jun 9 2007

Fingerprint

Average-case Analysis
Labeling Scheme
Labeling
Labels
Separator
Separators
Backbone
Operator

Keywords

  • Average case analysis
  • Separator
  • Tree labelling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, Ming-Yang ; Li, Xiang Yang ; Wang, Weizhao. / Average case analysis for tree labelling schemes. In: Theoretical Computer Science. 2007 ; Vol. 378, No. 3. pp. 271-291.
@article{f34ccc0bfdbb4d029f22cfc731e5d9e2,
title = "Average case analysis for tree labelling schemes",
abstract = "We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least frac(1, 8) log2 n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ (log n {dot operator} log (Hn (T))), where Hn (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.",
keywords = "Average case analysis, Separator, Tree labelling",
author = "Ming-Yang Kao and Li, {Xiang Yang} and Weizhao Wang",
year = "2007",
month = "6",
day = "9",
doi = "10.1016/j.tcs.2007.02.066",
language = "English (US)",
volume = "378",
pages = "271--291",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "3",

}

Average case analysis for tree labelling schemes. / Kao, Ming-Yang; Li, Xiang Yang; Wang, Weizhao.

In: Theoretical Computer Science, Vol. 378, No. 3, 09.06.2007, p. 271-291.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Average case analysis for tree labelling schemes

AU - Kao, Ming-Yang

AU - Li, Xiang Yang

AU - Wang, Weizhao

PY - 2007/6/9

Y1 - 2007/6/9

N2 - We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least frac(1, 8) log2 n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ (log n {dot operator} log (Hn (T))), where Hn (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.

AB - We study how to label the vertices of a tree in such a way that we can decide the distance of two vertices in the tree given only their labels. Gavoille et al. proved that for any such distance labelling scheme, the maximum label length is at least frac(1, 8) log2 n - O (log n) bits, where n is the number of vertices in the input tree T. They also gave a separator-based labelling scheme that has the optimal label length Θ (log n {dot operator} log (Hn (T))), where Hn (T) is the height of T. We present two distance labelling schemes, namely, the backbone-based scheme and rake-based scheme, which also achieve the optimal label length. The two schemes always perform at least as well as the separator scheme. Furthermore, the rake-based scheme has a much smaller expected label length under certain tree distributions. With these new schemes, we also can find the least common ancestor of any two vertices based on their labels only.

KW - Average case analysis

KW - Separator

KW - Tree labelling

UR - http://www.scopus.com/inward/record.url?scp=34248231997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34248231997&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2007.02.066

DO - 10.1016/j.tcs.2007.02.066

M3 - Article

AN - SCOPUS:34248231997

VL - 378

SP - 271

EP - 291

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 3

ER -