{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T09:41:56Z","timestamp":1746438116470},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540223399"},{"type":"electronic","value":"9783540278108"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27810-8_7","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T17:27:29Z","timestamp":1279042049000},"page":"64-76","source":"Crossref","is-referenced-by-count":6,"title":["Collective Tree Spanners of Graphs"],"prefix":"10.1007","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyu","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irina","family":"Lomonosov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 161\u2013168 (1998)","key":"7_CR1","DOI":"10.1145\/276698.276725"},{"key":"7_CR2","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. North-Holland, Amsterdam (1989)"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/3-540-36136-7_15","volume-title":"Algorithms and Computation","author":"F.F. Brandst\u00e4dt","year":"2002","unstructured":"Brandst\u00e4dt, F.F., Dragan, H.-O.: Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 163\u2013174. Springer, Heidelberg (2002)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-540-39890-5_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F.F. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, F.F., Dragan, H.-O., Le, V.B.: Tree spanners for bipartite graphs and probe interval graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 106\u2013118. Springer, Heidelberg (2003)"},{"key":"7_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"V.B. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, V.B., Le, J.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree spanners. SIAM J. Disc. Math.,\u00a08, 359\u2013387 (1995)","journal-title":"SIAM J. Disc. Math.,"},{"doi-asserted-by":"crossref","unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S.: Approximating a Finite Metric by a Small Number of Tree Metrics. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 379\u2013388 (1998)","key":"7_CR7","DOI":"10.1109\/SFCS.1998.743488"},{"key":"7_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-44849-7_16","volume-title":"Algorithms and Complexity","author":"V.D. Chepoi","year":"2003","unstructured":"Chepoi, V.D., Dragan, F.F., Yan, C.: Additive Spanners for k-Chordal Graphs. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol.\u00a02653, pp. 201\u2013212. Springer, Heidelberg (2003)"},{"doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Lomonosov, I.: Compact and efficient routing schemes for special graph classes (2004) (in preparation)","key":"7_CR9","DOI":"10.1007\/978-3-540-30551-4_36"},{"doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Yan, C.: Collective tree spanners of homogeneously orderable graphs (2004) (in preparation)","key":"7_CR10","DOI":"10.1007\/978-3-540-27810-8_7"},{"doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Yan, C., Corneil, D.G.: Collective tree spanners and routing in AT-free related graphs (2004) (in preparation)","key":"7_CR11","DOI":"10.1007\/978-3-540-30559-0_6"},{"key":"7_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/3-540-36108-1_17","volume-title":"Distributed Computing","author":"Y. Dourisboure","year":"2002","unstructured":"Dourisboure, Y., Gavoille, C.: Improved Compact Routing Scheme for Chordal Graphs. In: Malkhi, D. (ed.) DISC 2002. LNCS, vol.\u00a02508, pp. 252\u2013264. Springer, Heidelberg (2002)"},{"unstructured":"Dourisboure, Y., Gavoille, C.: Tree-length of graphs (2003)(manuscript)","key":"7_CR13"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in Trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 757\u2013772. Springer, Heidelberg (2001)"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1006\/jpdc.2000.1705","volume":"61","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Gengler, M.: Space-efficiency of routing schemes of stretch factor three. J. Parallel and Distr. Comput.\u00a061, 679\u2013687 (2001)","journal-title":"J. Parallel and Distr. Comput."},{"key":"7_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/3-540-46541-3_43","volume-title":"STACS 2000","author":"M. Katz","year":"2000","unstructured":"Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for well-separated graph classes. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 516\u2013528. Springer, Heidelberg (2000)"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/net.3230230417","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.: Additive graph spanners. Networks\u00a023, 343\u2013364 (1993)","journal-title":"Networks"},{"key":"7_CR18","volume-title":"SIAM Monographs on Discrete Math. Appl.","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. In: SIAM Monographs on Discrete Math. Appl., SIAM, Philadelphia (2000)"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph Spanners. J. Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"doi-asserted-by":"crossref","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. In: Proc. 6th ACM Symposium on Principles of Distributed Computing, Vancouver, pp. 77\u201385 (1987)","key":"7_CR20","DOI":"10.1145\/41840.41847"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1137\/S0895480195295471","volume":"17","author":"E. Prisner","year":"2003","unstructured":"Prisner, E., Kratsch, D., Le, H.-O., M\u00fcller, H., Wagner, D.: Additive tree spanners. SIAM Journal on Discrete Mathematics\u00a017, 332\u2013340 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"7_CR22","first-page":"1","volume-title":"Proc. 13th Ann. ACM Symp. on Par. Alg. and Arch. (SPAA 2001)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Thorup, M., Zwick, U. (eds.) Proc. 13th Ann. ACM Symp. on Par. Alg. and Arch (SPAA 2001), pp. 1\u201310. ACM Press, New York (2001)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27810-8_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:46Z","timestamp":1605759706000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27810-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540223399","9783540278108"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27810-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}