{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T05:55:16Z","timestamp":1769925316884,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,9,13]],"date-time":"2008-09-13T00:00:00Z","timestamp":1221264000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00453-008-9226-7","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T20:05:04Z","timestamp":1221249904000},"page":"641-652","source":"Crossref","is-referenced-by-count":7,"title":["Constructing Labeling Schemes through Universal Matrices"],"prefix":"10.1007","volume":"57","author":[{"given":"Amos","family":"Korman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoav","family":"Rodeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,9,13]]},"reference":[{"key":"9226_CR1","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. In: Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (2003)"},{"key":"9226_CR2","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/s00224-004-1155-5","volume":"37","author":"S. Alstrup","year":"2004","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new distributed algorithm. Theory Comput. Syst. 37, 441\u2013456 (2004)","journal-title":"Theory Comput. Syst."},{"key":"9226_CR3","unstructured":"Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: Proc. 12th ACM-SIAM Symp. on Discrete Algorithms (2001)"},{"key":"9226_CR4","unstructured":"Alstrup, S., Rauhe, T.: Improved labeling scheme for ancestor queries. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (2002)"},{"key":"9226_CR5","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Rauhe, T.: Small induced-universal graphs and compact implicit graph representations. In: Proc. 43rd IEEE Symp. on Foundations of Computer Science (2002)","DOI":"10.1109\/SFCS.2002.1181882"},{"issue":"4","key":"9226_CR6","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1002\/jgt.3190140408","volume":"14","author":"F.R.K. Chung","year":"1990","unstructured":"Chung, F.R.K.: Universal graphs and induced-universal graphs. J. Graph. Theory 14(4), 443\u2013454 (1990)","journal-title":"J. Graph. Theory"},{"key":"9226_CR7","doi-asserted-by":"crossref","unstructured":"\u00a0Cohen, E., \u00a0Halperin, E., \u00a0Kaplan, H., \u00a0Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms (2002)","DOI":"10.1137\/S0097539702403098"},{"key":"9226_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, E., Kaplan, H., Milo, T.: Labeling dynamic XML trees. In: Proc. 21st ACM Symp. on Principles of Database Systems (2002)","DOI":"10.1145\/543613.543648"},{"key":"9226_CR9","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Proc. 28th Int. Colloq. on Automata, Languages & Prog","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Proc. 28th Int. Colloq. on Automata, Languages & Prog. LNCS, vol. 2076, pp. 757\u2013772. Springer, Berlin (2001)"},{"key":"9226_CR10","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Paul, C.: Split decomposition and distance labelling: an optimal scheme for distance hereditary graphs. In: Proc. European Conf. on Combinatorics, Graph Theory and Applications (2001)","DOI":"10.1016\/S1571-0653(04)00374-9"},{"key":"9226_CR11","doi-asserted-by":"crossref","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. 16, 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"9226_CR12","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Proc. 9th European Symp. on Algorithms, pp. 476\u2013488 (2001)","DOI":"10.1007\/3-540-44676-1_40"},{"key":"9226_CR13","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. In: Proc. 12th ACM-SIAM Symp. on Discrete Algorithms, pp. 210\u2013219 (2001)"},{"key":"9226_CR14","doi-asserted-by":"crossref","unstructured":"Korman, A.: General compact labeling schemes for dynamic trees. In: Proc. 19th Symp. on Distributed Computing (2005)","DOI":"10.1007\/11561927_33"},{"key":"9226_CR15","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. In: 25th ACM Symp. on Principles of Distributed Computing (2006)","DOI":"10.1145\/1146381.1146389"},{"key":"9226_CR16","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S. Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5, 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"9226_CR17","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Milo, T.: Short and simple labels for small distances and other functions. In: Workshop on Algorithms and Data Structures (2001)","DOI":"10.1007\/3-540-44634-6_23"},{"key":"9226_CR18","unstructured":"Kaplan, H., Milo, T.: Parent and ancestor queries using a compact index. In: Proc. 20th ACM Symp. on Principles of Database Systems (2001)"},{"key":"9226_CR19","unstructured":"Kaplan, H., Milo, T., Shabo, R.: A comparison of labeling schemes for ancestor queries. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (2002)"},{"key":"9226_CR20","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (2002)"},{"key":"9226_CR21","doi-asserted-by":"crossref","unstructured":"Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for well-separated graph classes. In: Proc. 17th Symp. on Theoretical Aspects of Computer Science, pp. 516\u2013528 (2000)","DOI":"10.1007\/3-540-46541-3_43"},{"key":"9226_CR22","doi-asserted-by":"crossref","unstructured":"Korman, A., Peleg, D.: Labeling schemes for weighted dynamic trees. In: Proc. 30th Int. Colloq. on Automata, Languages & Prog. (2003)","DOI":"10.1007\/3-540-45061-0_31"},{"key":"9226_CR23","series-title":"SV-LNCS","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-3-540-75142-7_25","volume-title":"Proc. 21st Symp. on Distributed Computing","author":"A. Korman","year":"2007","unstructured":"Korman, A., Peleg, D.: Compact separator decompositions in dynamic trees and applications to labeling schemes. In: Proc. 21st Symp. on Distributed Computing. SV-LNCS, vol. 4731, pp. 313\u2013327. Springer, Berlin (2007)"},{"key":"9226_CR24","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s00224-003-1106-6","volume":"37","author":"A. Korman","year":"2004","unstructured":"Korman, A., Peleg, D., Rodeh, Y.: Labeling schemes for dynamic tree networks. Theory Comput. Syst. 37, 49\u201375 (2004)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"9226_CR25","first-page":"295","volume":"7","author":"V.V. Lozin","year":"1997","unstructured":"Lozin, V.V.: On minimal universal graphs for hereditary classes. J. Discrete Math. Appl. 7(3), 295\u2013304 (1997)","journal-title":"J. Discrete Math. Appl."},{"key":"9226_CR26","unstructured":"Lozin, V.V., Rudolf, G.: Minimal universal bipartite graphs. Ars Comb. 84 (2007)"},{"key":"9226_CR27","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1017\/S2040618500035139","volume":"7","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W.: On minimal n-universal graphs. Proc. Glasgow Math. Soc. 7, 32\u201333 (1965)","journal-title":"Proc. Glasgow Math. Soc."},{"key":"9226_CR28","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Proc. 25th Int. Workshop on Graph-Theoretic Concepts in Computer Science, pp. 30\u201341, June 1999","DOI":"10.1007\/3-540-46784-X_5"},{"key":"9226_CR29","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1016\/j.tcs.2005.03.015","volume":"340","author":"D. Peleg","year":"2005","unstructured":"Peleg, D.: Informative labeling schemes for graphs. Theor. Comput. Sci. 340, 577\u2013593 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9226_CR30","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"9226_CR31","doi-asserted-by":"crossref","unstructured":"Rado, R.: Universal graphs and universal functions. Acta Arith. 331\u2013340 (1964)","DOI":"10.4064\/aa-9-4-331-340"},{"key":"9226_CR32","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51, 993\u20131024 (2004)","journal-title":"J. ACM"},{"key":"9226_CR33","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proc. 13th ACM Symp. on Parallel Algorithms and Architecture, Hersonissos, Crete, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9226-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9226-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9226-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:02Z","timestamp":1559137502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9226-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,13]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["9226"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9226-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,9,13]]}}}