{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:42Z","timestamp":1760202522052},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_15","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"136-145","source":"Crossref","is-referenced-by-count":1,"title":["Average Case Analysis for Tree Labelling Schemes"],"prefix":"10.1007","author":[{"given":"Ming-Yang","family":"Kao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiang-Yang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WeiZhao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 689\u2013698 (2003)"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new distributed algorithm. In: SPAA 2002 (2002)","DOI":"10.1145\/564870.564914"},{"key":"15_CR3","unstructured":"Alstrup, S., Rauhe, T.: Lower bounds for labeling schemes supporting, ancestor, sibling, and connectivity queries. Tech. Report IT-C, nr. 10, IT University of Copenhagen (2001)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Rauhe, T.: Small induced universal graphs and compact implicit graph representations. In: IEEE FOCS (2002)","DOI":"10.1109\/SFCS.2002.1181882"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","volume":"12","author":"M.A. Breuer","year":"1966","unstructured":"Breuer, M.A.: Coding the vertexes of a graph. IEEE Transactions on Information Theory\u00a012, 148\u2013153 (1966)","journal-title":"IEEE Transactions on Information Theory"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/0022-247X(67)90082-0","volume":"20","author":"M.A. Breuer","year":"1967","unstructured":"Breuer, M.A., Folkman, J.: An unexpected result on coding the vertices of a graph. Journal of Mathematical Analysis and Applications\u00a020, 583\u2013600 (1967)","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"15_CR7","unstructured":"Gavoille, S.P.C., Peleg, D., Raz, R.: Distance labeling in graphs. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms, pp. 210\u2013219 (2001)"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0022-0000(82)90004-6","volume":"25","author":"P. Flajolet","year":"1982","unstructured":"Flajolet, P., Odlyzko, A.: The average height of binary trees and other simple trees. Journal of Computer and System Sciences\u00a025, 171\u2013213 (1982)","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Algorithms - ESA 2001","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 476\u2013488. Springer, Heidelberg (2001)"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput.\u00a016, 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"1592","DOI":"10.1137\/S0097539795283504","volume":"27","author":"M.-Y. Kao","year":"1998","unstructured":"Kao, M.-Y.: Tree contractions and evolutionary trees. SIAM Journal on Computing\u00a027, 1592\u20131616 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/3-540-46784-X_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Peleg","year":"1999","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 30\u201341. Springer, Heidelberg (1999)"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1145\/765568.765571","volume":"50","author":"B. Reed","year":"2003","unstructured":"Reed, B.: The height of a random binary search tree. Journal of ACM\u00a050, 306\u2013332 (2003)","journal-title":"Journal of ACM"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1145\/62212.62244","volume-title":"Proceedings of the Twentieth annual ACM symposium on Theory of computing","author":"M.N.S. Kannan","year":"1988","unstructured":"Kannan, M.N.S., Rudich, S.: Implicit representation of graphs. In: Proceedings of the Twentieth annual ACM symposium on Theory of computing, pp. 334\u2013343. ACM Press, New York (1988)"},{"key":"15_CR15","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)"},{"key":"15_CR16","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Englewood Cliffs (2000)","edition":"2"},{"key":"15_CR17","unstructured":"Kao, M.-Y., Li, X.-Y., Wang, W.: Average Case Analysis for Tree Labelling Schemes. Full veresion of the paper is available at, \n                    \n                      http:\/\/www.cs.iit.edu\/~xli\/publications-select.html"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:02:38Z","timestamp":1619506958000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11602613_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}