{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:33:42Z","timestamp":1725564822546},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540222309"},{"type":"electronic","value":"9783540277965"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27796-5_12","type":"book-chapter","created":{"date-parts":[[2010,9,5]],"date-time":"2010-09-05T21:47:42Z","timestamp":1283723262000},"page":"123-137","source":"Crossref","is-referenced-by-count":2,"title":["Sparse Additive Spanners for Bounded Tree-Length Graphs"],"prefix":"10.1007","author":[{"given":"Yon","family":"Dourisboure","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s003730200002","volume":"18","author":"N. Alon","year":"2002","unstructured":"Alon, N., Hoory, S., Linial, N.: The Moore bound for irregular graphs. Graph and Combinatorics\u00a018(1), 53\u201357 (2002)","journal-title":"Graph and Combinatorics"},{"issue":"1","key":"12_CR2","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09(1), 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k \u2212 1)-spanner of O(n1\u2009+\u20091\/k ) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025, 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"12_CR5","first-page":"1","volume":"3","author":"U. Brandes","year":"1998","unstructured":"Brandes, U., Handke, D.: NP-completeness results for minimum planar spanners. Discrete Mathematics & Theoretical Computer Science\u00a03(1), 1\u201310 (1998)","journal-title":"Discrete Mathematics & Theoretical Computer Science"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/S0304-3975(03)00424-9","volume":"310","author":"A. Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Van Bang, L.: Tree spanners on chordal graphs: Complexity and algorithms. Theoretical Computer Science\u00a0310, 329\u2013354 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"12_CR7","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 Journal on Discrete Mathematics\u00a08(3), 359\u2013387 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Chepoi, V.D., Dragan, F.F.: Distance approximating trees in graphs. In: Elsevier (ed.) 6th International Conference on Graph Theory (ICGT), August 2000. Electronical Notes in Discrete Mathematics (2000)","DOI":"10.1016\/S1571-0653(05)00731-6"},{"key":"12_CR9","doi-asserted-by":"crossref","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. 96\u2013107. Springer, Heidelberg (2003)","DOI":"10.1007\/3-540-44849-7_16"},{"key":"12_CR10","volume-title":"Graph Theory of Graduate Texts in Mathematics","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory of Graduate Texts in Mathematics, 2nd edn., vol.\u00a0173. Springer, Heidelberg (February 2000)","edition":"2"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Dodis, Y., Khanna, S.: Designing networks with bounded pairwise distance. In: 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 750\u2013759 (1999)","DOI":"10.1145\/301250.301447"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM Journal on Computing\u00a029, 1740\u20131759 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR13","unstructured":"Dourisboure, Y.: Routage compact et longueur arborescente. PhD thesis, Universit\u00e9 Bordeaux 1, Talence, France (December 2003)"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Dourisboure, Y., Dragan, F.F., Gavoille, C., Yan, C.: Improved spanners for bounded tree-length graphs (2004) (in preparation)","DOI":"10.1007\/978-3-540-27796-5_12"},{"key":"12_CR15","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decomposition of graphs with small diameter bags. In: 2nd European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB), September 2003, pp. 100\u2013104 (2003)"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Elkin, M., Peleg, D. (1+,\u03b5 \u03b2)-spanner constructions for general graphs. In: 33rd Annual ACM Symposium on Theory of Computing (STOC), July 2001, pp. 173\u2013182 (2001)","DOI":"10.1145\/380752.380797"},{"key":"12_CR17","unstructured":"Erd\u00f6s, P.: Extremal problems in graph theory. Publ. House Cszechoslovak Acad. Sci., Prague, 29\u201336 (1964)"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/S0166-218X(00)00226-2","volume":"108","author":"S.P. Fekete","year":"2001","unstructured":"Fekete, S.P., Kremer, J.: Tree spanners in planar graphs. Discrete Applied Mathematics\u00a0108, 85\u2013103 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Algorithms - ESA 2001","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 476\u2013488. Springer, Heidelberg (2001)"},{"issue":"2","key":"12_CR20","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(96)00078-6","volume":"59","author":"M.S. Madanlal","year":"1996","unstructured":"Madanlal, M.S., Venkatesan, G., Pandu Rangan, C.: Tree 3-spanners on interval, permutation and regular bipartite graphs. Information Processing Letters\u00a059(2), 97\u2013102 (1996)","journal-title":"Information Processing Letters"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"1","key":"12_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. Journal of Graph Theory\u00a013(1), 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchornizer for the hypercube. SIAM Journal on Computing\u00a018, 740\u2013747 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"12_CR24","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. Journal of the ACM\u00a036(3), 510\u2013530 (1989)","journal-title":"Journal of the ACM"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"key":"12_CR26","first-page":"225","volume":"89","author":"J. Soares","year":"1992","unstructured":"Soares, J.: Graphs spanners: A survey. Congressus Numerantium\u00a089, 225\u2013238 (1992)","journal-title":"Congressus Numerantium"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: 33rd Annual ACM Symposium on Theory of Computing (STOC), July 2001, pp. 183\u2013192 (2001)","DOI":"10.1145\/380752.380798"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27796-5_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:20:55Z","timestamp":1605759655000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27796-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540222309","9783540277965"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27796-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}