{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:25Z","timestamp":1725488545570},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540401766"},{"type":"electronic","value":"9783540448495"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44849-7_16","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:26:17Z","timestamp":1186741577000},"page":"96-107","source":"Crossref","is-referenced-by-count":7,"title":["Additive Spanners for k-Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Victor D.","family":"Chepoi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenyu","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"I. Alth\u00f6fer, G. Das, D. Dobkin, D. Joseph, and J. Soares, On sparse spanners of weighted graphs, Discrete Comput. Geom., 9 (1993), 81\u2013100.","journal-title":"Discrete Comput. Geom."},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-8858(86)90038-2","volume":"7","author":"H.-J. Bandelt","year":"1986","unstructured":"H.-J. Bandelt, A. Dress, Reconstructing the shape of a tree from observed dissimilarity data, Adv. Appl. Math. 7 (1986) 309\u2013343.","journal-title":"Adv. Appl. Math."},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"A. Brandst\u00e4dt, V. Chepoi and F. Dragan. Distance Approximating Trees for Chordal and Dually Chordal Graphs, Journal of Algorithms, 30 (1999), 166\u2013184.","journal-title":"Journal of Algorithms"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, F.F. Dragan, H.-O. Le, and V.B. Le, Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems, to appear in the Proceedings of ISAAC 2002.","DOI":"10.1007\/3-540-36136-7_15"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"U. Brandes and D. Handke, NP-Completeness Results for Minimum Planar Spanners, Preprint University of Konstanz, Konstanzer Schriften in Mathematik und Informatik, Nr. 16, Oktober 1996.","DOI":"10.1007\/BFb0024490"},{"key":"16_CR6","unstructured":"L. Cai, Tree spanners: Spanning trees that approximate the distances, Ph.D. thesis, University of Toronto, 1992."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"L. Cai and D.G. Corneil, Tree spanners, SIAM J. Disc. Math., 8 (1995), 359\u2013387.","journal-title":"SIAM J. Disc. Math."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1006\/eujc.1999.0381","volume":"21","author":"V. Chepoi","year":"2000","unstructured":"V. Chepoi and F. Dragan, A Note on Distance Approximating Trees in Graphs, Europ. J. Combinatorics, 21 (2000) 761\u2013766.","journal-title":"Europ. J. Combinatorics"},{"key":"16_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/3-540-45477-2_11","volume-title":"Proc. 27th International Workshop \u201cGraph-Theoretic Concepts in Computer Science\u201d (WG\u201901)","author":"F.F. Dragan","year":"2001","unstructured":"F.F. Dragan, Estimating All Pairs Shortest Paths in Restricted Graph Families: A Unified Approach (extended abstract), Proc. 27th International Workshop \u201cGraph-Theoretic Concepts in Computer Science\u201d (WG\u201901), June 2001, Springer, Lecture Notes in Computer Science 2204, pp. 103\u2013116."},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0166-218X(00)00226-2","volume":"108","author":"S.P. Fekete","year":"2001","unstructured":"S.P. Fekete, J. Kremer, Tree spanners in planar graphs, Discrete Appl. Math. 108 (2001) 85\u2013103.","journal-title":"Discrete Appl. Math."},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0605032","volume":"5","author":"J.R. Gilbert","year":"1984","unstructured":"J.R. Gilbert, D.J. Rose, and A. Edenbrandt, A separator theorem for chordal graphs, SIAM J. Alg. Discrete Math., 5 (1984) 306\u2013313.","journal-title":"SIAM J. Alg. Discrete Math."},{"key":"16_CR12","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"16_CR13","unstructured":"H.-O. Le, Effiziente Algorithmen f\u00fcr Baumspanner in chordalen Graphen, Diploma thesis, Dept. of mathematics, technical university of Berlin, 1994."},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<81::AID-NET1>3.0.CO;2-P","volume":"34","author":"H.-O. Le","year":"1999","unstructured":"H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (1999) 81\u201387.","journal-title":"Networks"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/net.3230230417","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"A.L. Liestman and T. Shermer, Additive graph spanners, Networks, 23 (1993), 343\u2013364.","journal-title":"Networks"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(96)00078-6","volume":"59","author":"M.S. Madanlal","year":"1996","unstructured":"M.S. Madanlal, G. Venkatesan and C. Pandu Rangan, Tree 3-spanners on interval, permutation and regular bipartite graphs, Information Processing Letters, 59 (1996), 97\u2013102.","journal-title":"Information Processing Letters"},{"key":"16_CR17","unstructured":"I.E. Papoutsakis, On the union of two tree spanners of a graph, Preprint, 2001."},{"key":"16_CR18","volume-title":"SIAM Monographs on Discrete Math. Appl.","author":"D. Peleg","year":"2000","unstructured":"D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM Monographs on Discrete Math. Appl., (SIAM, Philadelphia, 2000)."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"D. Peleg and A. A. Sch\u00e4ffer, Graph Spanners, Journal of Graph Theory, 13 (1989), 99\u2013116.","journal-title":"Journal of Graph Theory"},{"key":"16_CR20","doi-asserted-by":"crossref","unstructured":"D. Peleg and J.D. Ullman, An optimal synchronizer for the hypercube, in Proc. 6th ACM Symposium on Principles of Distributed Computing, Vancouver, 1987, 77\u201385.","DOI":"10.1145\/41840.41847"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"D. Peleg and E. Upfal, A tradeoff between space and efficiency for routing tables. 20th ACM Symposium on the Theory of Computing, Chicago (1988), 43\u201352.","DOI":"10.1145\/62212.62217"},{"key":"16_CR22","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/BFb0023484","volume-title":"Proc. of STACS\u201997","author":"E. Prisner","year":"1997","unstructured":"E. Prisner, Distance approximating spanning trees, in Proc. of STACS\u201997, Lecture Notes in Computer Science 1200, (R. Reischuk and M. Morvan, eds.), Springer-Verlag, Berlin, New York, 1997, 499\u2013510."},{"key":"16_CR23","unstructured":"E. Prisner, H.-O. Le, H. M\u00fcller and D. Wagner, Additive tree spanners, to appear in SIAM Journal on Discrete Mathematics."},{"key":"16_CR24","first-page":"225","volume":"89","author":"J. Soares","year":"1992","unstructured":"J. Soares, Graph spanners: A survey, Congressus Numer. 89 (1992) 225\u2013238.","journal-title":"Congressus Numer"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44849-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T22:12:28Z","timestamp":1556748748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44849-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540401766","9783540448495"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44849-7_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}