{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,30]],"date-time":"2025-01-30T05:50:27Z","timestamp":1738216227092,"version":"3.34.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-78773-0_48","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"555-567","source":"Crossref","is-referenced-by-count":0,"title":["Collective Additive Tree Spanners of Homogeneously Orderable 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":"Yang","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC 1998, pp. 161\u20138 (1998)","DOI":"10.1145\/276698.276725"},{"key":"48_CR2","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.F.: Distance Approximating Trees for Chordal and Dually Chordal Graphs. J. Algorithms\u00a030, 166\u2013184 (1999)","journal-title":"J. Algorithms"},{"key":"48_CR3","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Chepoi, V.D., Voloshin, V.I.: Dually chordal graphs. SIAM J. Discrete Math.\u00a011, 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"48_CR4","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0304-3975(96)00091-6","volume":"172","author":"A. Brandst\u00e4dt","year":"1997","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Nicolai, F.: Homogeneously orderable graphs. Theoretical Computer Science\u00a0172, 209\u2013232 (1997)","journal-title":"Theoretical Computer Science"},{"key":"48_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le Bang, V., Spinrad, J.P.: Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications. Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"48_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."},{"key":"48_CR7","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: FOCS 1998, pp. 379\u2013388 (1998)","DOI":"10.1109\/SFCS.1998.743488"},{"key":"48_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/11604686_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D.G. Corneil","year":"2005","unstructured":"Corneil, D.G., Dragan, F.F., K\u00f6hler, E., Yan, C.: Collective tree 1-spanners for interval graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 151\u2013162. Springer, Heidelberg (2005)"},{"key":"48_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/(SICI)1097-0037(199709)30:2<121::AID-NET6>3.0.CO;2-E","volume":"30","author":"F.F. Dragan","year":"1997","unstructured":"Dragan, F.F., Nicolai, F.: r-Domination Problems on Homogeneously Orderable Graphs. Networks\u00a030, 121\u2013131 (1997)","journal-title":"Networks"},{"key":"48_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/11602613_59","volume-title":"Algorithms and Computation","author":"F.F. Dragan","year":"2005","unstructured":"Dragan, F.F., Yan, C.: Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-width, or Clique-width. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 583\u2013592. Springer, Heidelberg (2005)"},{"key":"48_CR11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.7155\/jgaa.00120","volume":"10","author":"F.F. Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Corneil, D.G.: Collective Tree Spanners and Routing in AT-free Related Graphs. J. of Graph Algorithms and Applications\u00a010, 97\u2013122 (2006)","journal-title":"J. of Graph Algorithms and Applications"},{"key":"48_CR12","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1137\/S089548010444167X","volume":"20","author":"F.F. Dragan","year":"2006","unstructured":"Dragan, F.F., Yan, C., Lomonosov, I.: Collective tree spanners of graphs. SIAM J. Discrete Math.\u00a020, 241\u2013260 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"48_CR13","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. In: STOC 2003, pp. 448\u2013455 (2003)","DOI":"10.1145\/780542.780608"},{"key":"48_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":"48_CR15","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0605032","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"Gilbert, J.R., Rose, D.J., Edenbrandt, A.: A separator theorem for chordal graphs. SIAM J. Alg. Discrete Meth.\u00a05, 306\u2013313 (1984)","journal-title":"SIAM J. Alg. Discrete Meth."},{"key":"48_CR16","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1137\/S0097539702409927","volume":"34","author":"A. Gupta","year":"2005","unstructured":"Gupta, A., Kumar, A., Rastogi, R.: Traveling with a Pez Dispenser (or, Routing Issues in MPLS). SIAM J. Comput.\u00a034, 453\u2013474 (Also in FOCS 2001) (2005)","journal-title":"SIAM J. Comput."},{"key":"48_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":"48_CR18","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Math. Appl. (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"48_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BFb0023484","volume-title":"STACS 97","author":"E. Prisner","year":"1997","unstructured":"Prisner, E.: Distance approximating spanning trees. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 499\u2013510. Springer, Heidelberg (1997)"},{"key":"48_CR20","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA 2001, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T11:54:29Z","timestamp":1738151669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_48"}},"subtitle":["[Extended Abstract]"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540787723","9783540787730"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}