{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:41:26Z","timestamp":1725522086753},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540922476"},{"type":"electronic","value":"9783540922483"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","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-92248-3_11","type":"book-chapter","created":{"date-parts":[[2008,12,4]],"date-time":"2008-12-04T08:36:17Z","timestamp":1228379777000},"page":"110-121","source":"Crossref","is-referenced-by-count":1,"title":["Additive Spanners for Circle Graphs and Polygonal Graphs"],"prefix":"10.1007","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Derek G.","family":"Corneil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ekkehard","family":"K\u00f6hler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: FOCS 1996, pp. 184\u2013193 (1996)","key":"11_CR1","DOI":"10.1109\/SFCS.1996.548477"},{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: STOC 1998, pp. 161\u2013168 (1998)","key":"11_CR2","DOI":"10.1145\/276698.276725"},{"key":"11_CR3","volume-title":"Trees and Proximity Representations","author":"J.-P. Barth\u00e9lemy","year":"1991","unstructured":"Barth\u00e9lemy, J.-P., Gu\u00e9noche, A.: Trees and Proximity Representations. Wiley, New York (1991)"},{"doi-asserted-by":"crossref","unstructured":"Bhatt, S., Chung, F., Leighton, F., Rosenberg, A.: Optimal simulations of tree machines. In: FOCS 1986, pp. 274\u2013282 (1986)","key":"11_CR4","DOI":"10.1109\/SFCS.1986.38"},{"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)","key":"11_CR5","DOI":"10.1109\/SFCS.1998.743488"},{"key":"11_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. Discrete Math.\u00a08, 359\u2013387 (1995)","journal-title":"SIAM J. Discrete Math."},{"unstructured":"Corneil, D.G., Dragan, F.F., K\u00f6hler, E., Xiang, Y.: Lower Bounds for Collective Additive Tree Spanners (in preparation)","key":"11_CR7"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2005.05.017","volume":"347","author":"V.D. Chepoi","year":"2005","unstructured":"Chepoi, V.D., Dragan, F.F., Yan, C.: Additive Sparse Spanners for Graphs with Bounded Length of Largest Induced Cycle. Theoretical Computer Science\u00a0347, 54\u201375 (2005)","journal-title":"Theoretical Computer Science"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"L.P. Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. J. of Computer and System Sciences\u00a039, 205\u2013219 (1989)","journal-title":"J. of Computer and System Sciences"},{"key":"11_CR10","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)"},{"doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Corneil, D.G., K\u00f6hler, E., Xiang, Y.: Additive Spanners for Circle Graphs and Polygonal Graphs (manuscript, 2008), http:\/\/www.cs.kent.edu\/~dragan\/Coll-Spanners-Circle.pdf","key":"11_CR11","DOI":"10.1007\/978-3-540-92248-3_11"},{"key":"11_CR12","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":"11_CR13","doi-asserted-by":"publisher","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. Journal of Graph Algorithms and Applications\u00a010, 97\u2013122 (2006)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"11_CR14","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":"11_CR15","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jagm.1997.0883","volume":"26","author":"E.S. Elmallah","year":"1998","unstructured":"Elmallah, E.S., Stewart, L.: Polygon Graph Recognition. Journal of Algorithms\u00a026, 101\u2013140 (1998)","journal-title":"Journal of Algorithms"},{"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)","key":"11_CR16","DOI":"10.1145\/780542.780608"},{"key":"11_CR17","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"11_CR18","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 (2005)","journal-title":"SIAM J. Comput."},{"key":"11_CR19","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":"11_CR20","series-title":"SIAM Monographs on Discrete Math. Appl.","doi-asserted-by":"publisher","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 Monographs on Discrete Math. Appl. SIAM, Philadelphia (2000)"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-Preserving Labeling Schemes and Their Applications. J. of Graph Theory\u00a033, 167\u2013176 (2000)","journal-title":"J. of Graph Theory"},{"key":"11_CR22","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: PODC 1987, pp. 77\u201385 (1987)","key":"11_CR23","DOI":"10.1145\/41840.41847"},{"key":"11_CR24","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":"11_CR25","volume-title":"Numerical Taxonomy","author":"P.H.A. Sneath","year":"1973","unstructured":"Sneath, P.H.A., Sokal, R.R.: Numerical Taxonomy. W.H. Freeman, San Francisco (1973)"},{"key":"11_CR26","first-page":"411","volume-title":"Molecular Systematics","author":"D.L. Swofford","year":"1990","unstructured":"Swofford, D.L., Olsen, G.J.: Phylogeny reconstruction. In: Hillis, D.M., Moritz, C. (eds.) Molecular Systematics, pp. 411\u2013501. Sinauer Associates Inc., Sunderland (1990)"},{"doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA 2001, pp. 1\u201310 (2001)","key":"11_CR27","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92248-3_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T20:17:13Z","timestamp":1557951433000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92248-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922476","9783540922483"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92248-3_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}