{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T01:41:07Z","timestamp":1701999667755},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,17]],"date-time":"2007-10-17T00:00:00Z","timestamp":1192579200000},"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":[[2009,1]]},"DOI":"10.1007\/s00453-007-9089-3","type":"journal-article","created":{"date-parts":[[2007,10,16]],"date-time":"2007-10-16T14:50:19Z","timestamp":1192546219000},"page":"1-15","source":"Crossref","is-referenced-by-count":6,"title":["Labeling Schemes for Tree Representation"],"prefix":"10.1007","volume":"53","author":[{"given":"Reuven","family":"Cohen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,17]]},"reference":[{"key":"9089_CR1","first-page":"20","volume-title":"Proc. 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA)","author":"I. Abraham","year":"2004","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. In: Proc. 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp.\u00a020\u201324. ACM Press, New York (2004)"},{"key":"9089_CR2","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H. Attiya","year":"1998","unstructured":"Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, New York (1998)"},{"key":"9089_CR3","first-page":"1396","volume":"14","author":"Y. Chu","year":"1965","unstructured":"Chu, Y., Liu, T.: On the shortest arborescence of a directed graph. Sci. Sinica 14, 1396\u20131400 (1965)","journal-title":"Sci. Sinica"},{"key":"9089_CR4","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: Proc. 32nd Int. Colloq. on Automata, Languages & Prog. (ICALP). Lecture Notes of Computer Science, vol.\u00a03580, pp.\u00a0335\u2013346 (2005)","DOI":"10.1007\/11523468_28"},{"key":"9089_CR5","doi-asserted-by":"crossref","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC). Lecture Notes of Computer Science, vol. 3741, pp.\u00a013\u201324 (2005)","DOI":"10.1007\/11603771_2"},{"key":"9089_CR6","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press\/McGraw-Hill (1990)"},{"key":"9089_CR7","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Strothmann, W.-B.: Bounded-degree spanning tree. In: Proc. 5th European Symp. on Algorithms (ESA). Lecture Notes of Computer Science, vol.\u00a01284, pp.\u00a0104\u2013117 (1997)","DOI":"10.1007\/3-540-63397-9_9"},{"key":"9089_CR8","unstructured":"Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. In: Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp.\u00a0588\u2013597 (2002)"},{"key":"9089_CR9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Stand. 71B, 233\u2013240 (1967)","journal-title":"J. Res. Nat. Bur. Stand."},{"issue":"2","key":"9089_CR10","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","volume":"21","author":"P. Elias","year":"1975","unstructured":"Elias, P.: Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 21(2), 194\u2013203 (1975)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9089_CR11","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Proc. 28th Int. Colloq. on Automata, Languages & Prog. (ICALP). Lecture Notes of Computer Science, vol.\u00a02076, pp.\u00a0757\u2013772 (July 2001)","DOI":"10.1007\/3-540-48224-5_62"},{"key":"9089_CR12","unstructured":"F\u00fcrer, M., Raghavachari, B.: Approximating the minimum degree spanning tree within one from the optimal degree. In: Proc. 3rd ACM-SIAM Sump. on Discrete Algorithms (SODA), pp.\u00a0317\u2013324 (1992)"},{"issue":"1","key":"9089_CR13","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"R.G. Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9089_CR14","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"J. Garay","year":"1998","unstructured":"Garay, J., Kutten, S., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27, 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9089_CR15","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Tarjan, R.: The planar Hamiltonian circuit is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9089_CR16","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1109\/TCOM.1983.1095883","volume":"31","author":"P. Humblet","year":"1983","unstructured":"Humblet, P.: A distributed algorithm for minimum weighted directed spanning trees. IEEE Trans. Commun. 31(6), 756\u2013762 (1983)","journal-title":"IEEE Trans. Commun."},{"key":"9089_CR17","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. Descrete Math. 5, 596\u2013603 (1992)","journal-title":"SIAM J. Descrete Math."},{"key":"9089_CR18","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M. Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34, 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"9089_CR19","doi-asserted-by":"crossref","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: Proc. the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), Las Vegas, NV, USA (2005)","DOI":"10.1145\/1073814.1073817"},{"key":"9089_CR20","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten, S., Fast distributed construction of k-dominating sets and applications. J. Algorithms 28, 40\u201366 (1998)","journal-title":"J. Algorithms"},{"key":"9089_CR21","volume-title":"Distributed Algorithms","author":"N. Lynch","year":"1995","unstructured":"Lynch, N.: Distributed Algorithms. Morgan Kaufmann, Los Altos (1995)"},{"key":"9089_CR22","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":"9089_CR23","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9089-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9089-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9089-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9089-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,17]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["9089"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9089-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,17]]}}}