Average case analysis for tree labelling schemes

Ming-Yang Kao; Xiang Yang Li; Weizhao Wang

doi:10.1007/11602613_15

Average case analysis for tree labelling schemes

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

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

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. For trees, Gavoille et al. [7] proved that for any such distance labelling scheme, the maximum label length is at least 1/8 log² n - O(log n) bits. They also gave a separator-based labelling scheme that has the optimal label length Θ(log n · log(H_n(T))), where H_n(T) is the height of the tree. In this paper, we present two new distance labelling schemes that not only achieve the optimal label length Θ (log n · log(H_n(T))), but also have a much smaller expected label length under certain tree distributions. With these new schemes, we also can efficiently find the least common ancestor of any two vertices based on their labels only.

Original language	English (US)
Title of host publication	Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings
Pages	136-145
Number of pages	10
DOIs	https://doi.org/10.1007/11602613_15
State	Published - 2005
Event	16th International Symposium on Algorithms and Computation, ISAAC 2005 - Hainan, China Duration: Dec 19 2005 → Dec 21 2005

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3827 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th International Symposium on Algorithms and Computation, ISAAC 2005
Country/Territory	China
City	Hainan
Period	12/19/05 → 12/21/05

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/11602613_15

Cite this

Kao, M-Y., Li, X. Y., & Wang, W. (2005). Average case analysis for tree labelling schemes. In Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings (pp. 136-145). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS). https://doi.org/10.1007/11602613_15

@inproceedings{cf93164c3422443fb33881f4a8662d83,

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. For trees, Gavoille et al. [7] proved that for any such distance labelling scheme, the maximum label length is at least 1/8 log2 n - O(log n) bits. They also gave a separator-based labelling scheme that has the optimal label length Θ(log n · log(Hn(T))), where Hn(T) is the height of the tree. In this paper, we present two new distance labelling schemes that not only achieve the optimal label length Θ (log n · log(Hn(T))), but also have a much smaller expected label length under certain tree distributions. With these new schemes, we also can efficiently find the least common ancestor of any two vertices based on their labels only.",

author = "Ming-Yang Kao and Li, {Xiang Yang} and Weizhao Wang",

note = "Funding Information: First author{\textquoteright}s research supported in part by NSF Grant IIS-0121491.; 16th International Symposium on Algorithms and Computation, ISAAC 2005 ; Conference date: 19-12-2005 Through 21-12-2005",

year = "2005",

doi = "10.1007/11602613_15",

language = "English (US)",

isbn = "3540309357",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "136--145",

booktitle = "Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings",

}

Kao, M-Y, Li, XY & Wang, W 2005, Average case analysis for tree labelling schemes. in Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3827 LNCS, pp. 136-145, 16th International Symposium on Algorithms and Computation, ISAAC 2005, Hainan, China, 12/19/05. https://doi.org/10.1007/11602613_15

Average case analysis for tree labelling schemes. / Kao, Ming-Yang; Li, Xiang Yang; Wang, Weizhao.
Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings. 2005. p. 136-145 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3827 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Average case analysis for tree labelling schemes

AU - Kao, Ming-Yang

AU - Li, Xiang Yang

AU - Wang, Weizhao

N1 - Funding Information: First author’s research supported in part by NSF Grant IIS-0121491.

PY - 2005

Y1 - 2005

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. For trees, Gavoille et al. [7] proved that for any such distance labelling scheme, the maximum label length is at least 1/8 log2 n - O(log n) bits. They also gave a separator-based labelling scheme that has the optimal label length Θ(log n · log(Hn(T))), where Hn(T) is the height of the tree. In this paper, we present two new distance labelling schemes that not only achieve the optimal label length Θ (log n · log(Hn(T))), but also have a much smaller expected label length under certain tree distributions. With these new schemes, we also can efficiently 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. For trees, Gavoille et al. [7] proved that for any such distance labelling scheme, the maximum label length is at least 1/8 log2 n - O(log n) bits. They also gave a separator-based labelling scheme that has the optimal label length Θ(log n · log(Hn(T))), where Hn(T) is the height of the tree. In this paper, we present two new distance labelling schemes that not only achieve the optimal label length Θ (log n · log(Hn(T))), but also have a much smaller expected label length under certain tree distributions. With these new schemes, we also can efficiently find the least common ancestor of any two vertices based on their labels only.

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

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

U2 - 10.1007/11602613_15

DO - 10.1007/11602613_15

M3 - Conference contribution

AN - SCOPUS:33744960547

SN - 3540309357

SN - 9783540309352

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 136

EP - 145

BT - Algorithms and Computation - 16th International Symposium, ISAAC 2005, Proceedings

T2 - 16th International Symposium on Algorithms and Computation, ISAAC 2005

Y2 - 19 December 2005 through 21 December 2005

ER -

Average case analysis for tree labelling schemes

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this