{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:21:40Z","timestamp":1761805300493},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,3,14]],"date-time":"2013-03-14T00:00:00Z","timestamp":1363219200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s00453-013-9765-4","type":"journal-article","created":{"date-parts":[[2013,3,13]],"date-time":"2013-03-13T12:29:40Z","timestamp":1363177780000},"page":"884-905","source":"Crossref","is-referenced-by-count":25,"title":["An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs"],"prefix":"10.1007","volume":"69","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[]},{"given":"Ekkehard","family":"K\u00f6hler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,14]]},"reference":[{"key":"9765_CR1","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1109\/FOCS.2008.62","volume-title":"Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)","author":"I. Abraham","year":"2008","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Nearly tight low stretch spanning trees. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), Philadelphia, PA, USA, 25\u201328 October 2008, pp.\u00a0781\u2013790. IEEE Comput. Soc., Los Alamitos (2008)"},{"key":"9765_CR2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.B.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24, 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"key":"9765_CR3","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0022-0000(86)90018-8","volume":"33","author":"G. Ausiello","year":"1986","unstructured":"Ausiello, G., D\u2019Arti, A., Moscarini, M.: Chordality properties on graphs and minimal conceptual connections in semantic data models. J. Comput. Syst. Sci. 33, 179\u2013202 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"9765_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-3-540-85363-3_3","volume-title":"Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX-RANDOM 2008)","author":"M. B\u01cedoiu","year":"2008","unstructured":"B\u01cedoiu, M., Demaine, E.D., Hajiaghayi, M.T., Sidiropoulos, A., Zadimoghaddam, M.: Ordinal embedding: approximation algorithms and dimensionality reduction. In: Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX-RANDOM 2008), Boston, MA, USA, 25\u201327 August 2008. Lecture Notes in Computer Science, vol.\u00a05171, pp.\u00a021\u201334. Springer, Berlin (2008)"},{"key":"9765_CR5","first-page":"512","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007)","author":"M. B\u01cedoiu","year":"2007","unstructured":"B\u01cedoiu, M., Indyk, P., Sidiropoulos, A.: Approximation algorithms for embedding general metrics into trees. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), New Orleans, Louisiana, 7\u20139 January 2007, pp.\u00a0512\u2013521. SIAM, Philadelphia (2007)"},{"key":"9765_CR6","first-page":"479","volume":"30","author":"C. Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J.\u00a0ACM 30, 479\u2013513 (1983)","journal-title":"J.\u00a0ACM"},{"key":"9765_CR7","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. North-Holland, Amsterdam (1989)"},{"key":"9765_CR8","doi-asserted-by":"crossref","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.: Distance approximating trees for chordal and dually chordal graphs. J. Algorithms 30, 166\u2013184 (1999)","journal-title":"J. Algorithms"},{"key":"9765_CR9","doi-asserted-by":"crossref","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., Le, V.B.: Tree spanners on chordal graphs: complexity and algorithms. Theor. Comput. Sci. 310, 329\u2013354 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9765_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s00453-006-1209-y","volume":"47","author":"A. Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Le, V.B., Uehara, R.: Tree spanners for bipartite graphs and probe interval graphs. Algorithmica 47, 27\u201351 (2007)","journal-title":"Algorithmica"},{"key":"9765_CR11","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"9765_CR12","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"A. Buneman","year":"1974","unstructured":"Buneman, A.: A characterization of rigid circuit graphs. Discrete Math. 9, 205\u2013212 (1974)","journal-title":"Discrete Math."},{"key":"9765_CR13","doi-asserted-by":"crossref","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. 8, 359\u2013387 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"9765_CR14","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1006\/eujc.1999.0381","volume":"21","author":"V. Chepoi","year":"2000","unstructured":"Chepoi, V., Dragan, F.: A note on distance approximating trees in graphs. Eur. J. Comb. 21, 761\u2013766 (2000)","journal-title":"Eur. J. Comb."},{"key":"9765_CR15","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","volume":"62","author":"V.D. Chepoi","year":"2012","unstructured":"Chepoi, V.D., Dragan, F.F., Estellon, B., Habib, M., Vaxes, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for \u03b4-hyperbolic graphs. Algorithmica 62, 713\u2013732 (2012)","journal-title":"Algorithmica"},{"key":"9765_CR16","first-page":"59","volume-title":"Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008)","author":"V. Chepoi","year":"2008","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of \u03b4-hyperbolic geodesic spaces and graphs. In: Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), College Park, Maryland, USA, 9\u201311 June 2008, pp.\u00a059\u201368. ACM, New York (2008)"},{"key":"9765_CR17","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s00454-011-9386-0","volume":"47","author":"V.D. Chepoi","year":"2012","unstructured":"Chepoi, V.D., Dragan, F.F., Newman, I., Rabinovich, Y., Vaxes, Y.: Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs. Discrete Comput. Geom. 47, 187\u2013214 (2012)","journal-title":"Discrete Comput. Geom."},{"key":"9765_CR18","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 347, 54\u201375 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9765_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BFb0056478","volume-title":"Proceedings of the 12th International Symposium on Distributed Computing (DISC 1998)","author":"M.J. Demmer","year":"1998","unstructured":"Demmer, M.J., Herlihy, M.: The arrow distributed directory protocol. In: Proceedings of the 12th International Symposium on Distributed Computing (DISC 1998), Andros, Greece, 24\u201326 September 1998. Lecture Notes in Computer Science, vol.\u00a01499, pp.\u00a0119\u2013133. Springer, Berlin (1998)"},{"key":"9765_CR20","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, 2nd edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2000)","edition":"2"},{"key":"9765_CR21","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2007.03.058","volume":"383","author":"Y. Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Dragan, F.F., Gavoille, C., Yan, C.: Spanners for bounded tree-length graphs. Theor. Comput. Sci. 383, 34\u201344 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9765_CR22","doi-asserted-by":"crossref","first-page":"2008","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y. Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Math. 307, 2008\u20132009 (2007)","journal-title":"Discrete Math."},{"key":"9765_CR23","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1016\/j.jcss.2010.10.002","volume":"77","author":"F.F. Dragan","year":"2011","unstructured":"Dragan, F.F., Fomin, F., Golovach, P.: Spanners in sparse graphs. J. Comput. Syst. Sci. 77, 1108\u20131119 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9765_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/978-3-642-22935-0_15","volume-title":"Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX-RANDOM 2011)","author":"F.F. Dragan","year":"2011","unstructured":"Dragan, F.F., K\u00f6hler, E.: An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs. In: Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX-RANDOM 2011), Princeton, NJ, USA, 17\u201319 August 2011. Lecture Notes in Computer Science, vol.\u00a06845, pp.\u00a0171\u2013183. Springer, Berlin (2011)"},{"key":"9765_CR25","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/050641661","volume":"38","author":"M. Elkin","year":"2008","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.-H.: Lower-stretch spanning trees. SIAM J. Comput. 38, 608\u2013628 (2008)","journal-title":"SIAM J. Comput."},{"key":"9765_CR26","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/j.tcs.2004.11.022","volume":"337","author":"M. Elkin","year":"2005","unstructured":"Elkin, M., Peleg, D.: Approximating k-spanner problems for k\u22652. Theor. Comput. Sci. 337, 249\u2013277 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9765_CR27","doi-asserted-by":"crossref","first-page":"1761","DOI":"10.1137\/060666202","volume":"38","author":"Y. Emek","year":"2008","unstructured":"Emek, Y., Peleg, D.: Approximating minimum max-stretch spanning trees on unweighted graphs. SIAM J. Comput. 38, 1761\u20131781 (2008)","journal-title":"SIAM J. Comput."},{"key":"9765_CR28","doi-asserted-by":"crossref","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 Appl. Math. 108, 85\u2013103 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9765_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Proceedings of the 9th Annual European Symposium on 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: Proceedings of the 9th Annual European Symposium on Algorithms (ESA 2001), Aarhus, Denmark, 28\u201331 August 2001. Lecture Notes in Computer Science, vol.\u00a02161, pp.\u00a0476\u2013488. Springer, Berlin (2001)"},{"key":"9765_CR30","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Ser. B 16, 47\u201356 (1974)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9765_CR31","doi-asserted-by":"crossref","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. Algebr. Discrete Methods 5, 306\u2013313 (1984)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9765_CR32","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1287\/trsc.5.2.212","volume":"5","author":"A.J. Goldman","year":"1971","unstructured":"Goldman, A.J.: Optimal center location in simple networks. Transp. Sci. 5, 212\u2013221 (1971)","journal-title":"Transp. Sci."},{"key":"9765_CR33","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1007\/s00224-006-1251-9","volume":"39","author":"M. Herlihy","year":"2006","unstructured":"Herlihy, M., Kuhn, F., Tirthapura, S., Wattenhofer, R.: Dynamic analysis of the arrow distributed protocol. Theory Comput. Syst. 39, 875\u2013901 (2006)","journal-title":"Theory Comput. Syst."},{"key":"9765_CR34","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1137\/S0895480195295471","volume":"17","author":"D. Kratsch","year":"2003","unstructured":"Kratsch, D., Le, H.-O., M\u00fcller, H., Prisner, E., Wagner, D.: Additive tree spanners. SIAM J. Discrete Math. 17, 332\u2013340 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9765_CR35","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1016\/j.dam.2007.07.001","volume":"156","author":"C. Liebchen","year":"2008","unstructured":"Liebchen, C., W\u00fcnsch, G.: The zoo of tree spanner problems. Discrete Appl. Math. 156, 569\u2013587 (2008)","journal-title":"Discrete Appl. Math."},{"key":"9765_CR36","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1016\/j.dam.2009.10.007","volume":"158","author":"D. Lokshtanov","year":"2010","unstructured":"Lokshtanov, D.: On the complexity of computing tree-length. Discrete Appl. Math. 158, 820\u2013827 (2010)","journal-title":"Discrete Appl. Math."},{"key":"9765_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1007\/3-540-45687-2_5","volume-title":"Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002)","author":"D. Peleg","year":"2002","unstructured":"Peleg, D.: Low stretch spanning trees. In: Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002). Lecture Notes in Computer Science, vol. 2420, pp.\u00a068\u201380. Springer, Berlin (2002)"},{"key":"9765_CR38","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1006\/jcss.2001.1787","volume":"63","author":"D. Peleg","year":"2001","unstructured":"Peleg, D., Reshef, E.: Low complexity variants of the arrow distributed directory. J. Comput. Syst. Sci. 63, 474\u2013485 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9765_CR39","unstructured":"Peleg, D., Tendler, D.: Low stretch spanning trees for planar graphs. Technical Report MCS01-14, Weizmann Science Press of Israel, Israel (2001)"},{"key":"9765_CR40","unstructured":"Makowsky, J.A., Rotics, U.: Optimal spanners in partial k-trees. Manuscript"},{"key":"9765_CR41","doi-asserted-by":"crossref","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. J. Algorithms 7, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"9765_CR42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/378580.378581","volume-title":"Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), Heraklion, Crete, Greece, 4\u20136 July 2001, pp.\u00a01\u201310. ACM, New York (2001)"},{"key":"9765_CR43","unstructured":"Walter, J.R.: Representations of rigid cycle graphs. Ph.D. Thesis, Wayne State University, Detroit (1972)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9765-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9765-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9765-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:11Z","timestamp":1559123111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9765-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,14]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["9765"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9765-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,14]]}}}