{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T03:05:31Z","timestamp":1768273531734,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,11,20]],"date-time":"2015-11-20T00:00:00Z","timestamp":1447977600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0094-7","type":"journal-article","created":{"date-parts":[[2015,11,20]],"date-time":"2015-11-20T09:49:02Z","timestamp":1448012942000},"page":"686-713","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Line-Distortion, Bandwidth and Path-Length of a Graph"],"prefix":"10.1007","volume":"77","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ekkehard","family":"K\u00f6hler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Leitert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"key":"94_CR1","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"SF Assman","year":"1981","unstructured":"Assman, S.F., Peck, G.W., Syslo, M.M., Zak, J.: The bandwidth of caterpillars with hairs of length 1 and 2. SIAM J. Algebraic Discrete Methods 2, 387\u2013392 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"94_CR2","unstructured":"Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem, Technical report TR98-014. University of Bonn (1997)"},{"key":"94_CR3","doi-asserted-by":"crossref","unstructured":"B\u0103doiu, M., Chuzhoy, J., Indyk, P., Sidiropoulos, A.: Low-distortion embeddings of general metrics into the line, In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005). Baltimore, MD, USA, ACM, pp. 225\u2013233, 22\u201324 May 2005","DOI":"10.1145\/1060590.1060624"},{"key":"94_CR4","unstructured":"B\u01cedoiu, M., Dhamdhere, K., Gupta, A., Rabinovich, Y., Raecke, H., Ravi, R., Sidiropoulos, A.: Approximation algorithms for low-distortion embeddings into low-dimensional spaces, In: Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms, (2005)"},{"key":"94_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"3","key":"94_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"94_CR7","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"DG Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM J. Discrete Math. 10, 399\u2013430 (1997)","journal-title":"SIAM J. Discrete Math."},{"key":"94_CR8","first-page":"292","volume":"28","author":"DG Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput. 28, 292\u2013302 (1997)","journal-title":"SIAM J. Comput."},{"key":"94_CR9","volume-title":"Graph Theory (Graduate Texts in Mathematics)","author":"R Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory (Graduate Texts in Mathematics), 2nd edn. Springer, Berlin (2000)","edition":"2"},{"key":"94_CR10","doi-asserted-by":"crossref","first-page":"208","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, 208\u2013229 (2007)","journal-title":"Discrete Math."},{"key":"94_CR11","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., K\u00f6hler, E.: An Approximation Algorithm for the tree $$t$$ t -spanner problem on unweighted graphs via generalized chordal graphs, approximation, randomization, and combinatorial optimization. algorithms and techniques. In: Proceedings of the 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, 17\u201319 Aug 2011. Lecture Notes in Computer Science 6845, Springer, pp. 171\u2013183; Algorithmica 69 (2014), 884\u2013905","DOI":"10.1007\/978-3-642-22935-0_15"},{"key":"94_CR12","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., K\u00f6hler, E., Leitert, A.: Line-distortion, Bandwidth and path-length of a graph. In Proceedings of 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014), July 2-4 2014. Copenhagen, Denmark, Lecture Notes in Computer Science 8503, pp. 146\u2013257 (2014)","DOI":"10.1007\/978-3-319-08404-6_14"},{"key":"94_CR13","doi-asserted-by":"crossref","unstructured":"Dubey, Ch., Feige, U., Unger, W.: Hardness results for approximating the bandwidth. J. Comput. Syst. Sci. 77, 62\u201390 (2011)","DOI":"10.1016\/j.jcss.2010.06.006"},{"key":"94_CR14","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1006\/jcss.1999.1682","volume":"60","author":"U Feige","year":"2000","unstructured":"Feige, U.: Approximating the bandwidth via volume respecting embedding. J. Comput. Syst. Sci. 60, 510\u2013539 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"94_CR15","doi-asserted-by":"crossref","unstructured":"Feige, U., Talwar, K.: Approximating the bandwidth of caterpillars. In: Proceedings of 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2005) and 9th International Workshop on Randomization and Computation (RANDOM 2005), Berkeley, CA, USA, Lecture Notes in Computer Science 3624, 2005, pp 62\u201373, 22\u201324 Aug 2005","DOI":"10.1007\/11538462_6"},{"key":"94_CR16","doi-asserted-by":"crossref","first-page":"16.1","DOI":"10.1145\/2489789","volume":"5","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Losievskaja, E., Rosamond, F.A., Saurabh, S.: Distortion is fixed parameter tractable. ACM Trans. Comput. Theory 5, 16.1\u201316.20 (2013)","journal-title":"ACM Trans. Comput. Theory"},{"key":"94_CR17","doi-asserted-by":"crossref","first-page":"3530","DOI":"10.1016\/j.tcs.2011.02.043","volume":"412","author":"FV Fomin","year":"2011","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: An exact algorithm for minimum distortion embedding. Theor. Comput. Sci. 412, 3530\u20133536 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR18","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"94_CR19","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and interval graphs. Can. J. Math. 16, 539\u2013548 (1964)","journal-title":"Can. J. Math."},{"key":"94_CR20","doi-asserted-by":"crossref","first-page":"7001","DOI":"10.1016\/j.tcs.2011.09.011","volume":"412","author":"PA Golovach","year":"2011","unstructured":"Golovach, P.A., Heggernes, P., Kratsch, D., Lokshtanov, D., Meister, D., Saurabh, S.: Bandwidth on AT-free graphs. Theor. Comput. Sci. 412, 7001\u20137008 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR21","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"94_CR22","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"MC Golumbic","year":"1983","unstructured":"Golumbic, M.C., Rotem, D., Urrutia, J.: Comparability graphs and intersection graphs. Discrete Math. 43, 37\u201346 (1983)","journal-title":"Discrete Math."},{"key":"94_CR23","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jagm.2000.1118","volume":"40","author":"A Gupta","year":"2001","unstructured":"Gupta, A.: Improved bandwidth approximation for trees and chordal graphs. J. Algorithms 40, 24\u201336 (2001)","journal-title":"J. Algorithms"},{"key":"94_CR24","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/j.jda.2008.11.001","volume":"7","author":"P Heggernes","year":"2009","unstructured":"Heggernes, P., Kratsch, D., Meister, D.: Bandwidth of bipartite permutation graphs in polynomial time. J. Discrete Algorithms 7, 533\u2013544 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"94_CR25","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/j.ipl.2010.02.009","volume":"110","author":"P Heggernes","year":"2010","unstructured":"Heggernes, P., Meister, D.: Hardness and approximation of minimum distortion embeddings. Inf. Process. Lett. 110, 312\u2013316 (2010)","journal-title":"Inf. Process. Lett."},{"key":"94_CR26","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1016\/j.tcs.2011.01.005","volume":"412","author":"P Heggernes","year":"2011","unstructured":"Heggernes, P., Meister, D., Proskurowski, A.: Computing minimum distortion embeddings into a path of bipartite permutation graphs and threshold graphs. Theor. Comput. Sci. 412, 1275\u20131297 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"94_CR27","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science (FOCS 2001). IEEE, pp. 10\u201335","DOI":"10.1109\/SFCS.2001.959878"},{"key":"94_CR28","doi-asserted-by":"crossref","unstructured":"Indyk, P., Matousek, J.: Low-distortion embeddings of finite metric spaces. In: Goodman J.E., O\u2019Rourke J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn., pp. 177\u2013196. CRC press, New York (2004)","DOI":"10.1201\/9781420035315.ch8"},{"key":"94_CR29","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1137\/0403033","volume":"3","author":"DJ Kleitman","year":"1990","unstructured":"Kleitman, D.J., Vohra, R.V.: Computing the bandwidth of interval graphs. SIAM J. Discrete Math. 3, 373\u2013375 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"94_CR30","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/jagm.1998.0997","volume":"32","author":"T Kloks","year":"1999","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Approximating the bandwidth for asteroidal triple-free graphs. J. Algorithms 32, 41\u201357 (1999)","journal-title":"J. Algorithms"},{"key":"94_CR31","unstructured":"Kratsch, D., Spinrad, J.: Between $${\\cal O}(n m)$$ O ( n m ) , In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2003). ACM, pp. 709\u2013716"},{"key":"94_CR32","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1137\/S0895480199359624","volume":"15","author":"D Kratsch","year":"2002","unstructured":"Kratsch, D., Stewart, L.: Approximating bandwidth by mixing layouts of interval graphs. SIAM J. Discrete Math. 15, 435\u2013449 (2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"7","key":"94_CR33","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 treelength. Discrete Appl. Math. 158(7), 820\u2013827 (2010)","journal-title":"Discrete Appl. Math."},{"key":"94_CR34","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/jagm.1994.1034","volume":"17","author":"TH Ma","year":"1994","unstructured":"Ma, T.H., Spinrad, J.P.: On the two-chain subgraph cover and related problems. J. Algorithms 17, 251\u2013268 (1994)","journal-title":"J. Algorithms"},{"key":"94_CR35","unstructured":"McConnell, R.M., Spinrad, J.P.: Linear-time transitive orientation. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, Louisiana 5\u20137, 19\u201325 (1997)"},{"key":"94_CR36","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B Monien","year":"1986","unstructured":"Monien, B.: The bandwidth-minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebraic Discrete Methods 7, 505\u2013512 (1986)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"94_CR37","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0020-0190(91)90245-D","volume":"37","author":"S Olariu","year":"1991","unstructured":"Olariu, S.: An optimal greedy heuristic to color interval graphs. Inf. Process. Lett. 37, 65\u201380 (1991)","journal-title":"Inf. Process. Lett."},{"key":"94_CR38","first-page":"167","volume":"3","author":"A Proskurowski","year":"1999","unstructured":"Proskurowski, A., Telle, J.A.: Classes of graphs with restricted interval models. Discrete Math. Theor. Comput. Sci. 3, 167\u2013176 (1999)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"94_CR39","unstructured":"R\u00e4cke, H.: Lecture notes at http:\/\/ttic.uchicago.edu\/~harry\/teaching\/pdf\/lecture15"},{"key":"94_CR40","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.: Graph minors. I. Excluding a forest. J. Comb. Theory Ser. B 35, 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"94_CR41","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1016\/j.ipl.2012.02.012","volume":"112","author":"AMS Shrestha","year":"2012","unstructured":"Shrestha, A.M.S., Tayu, S., Ueno, S.: Bandwidth of convex bipartite graphs and related graphs. Inf. Process. Lett. 112, 411\u2013417 (2012)","journal-title":"Inf. Process. Lett."},{"key":"94_CR42","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1137\/S0895480192232333","volume":"7","author":"AP Sprague","year":"1994","unstructured":"Sprague, A.P.: An $${\\cal O}(n \\log n)$$ O ( n log n ) algorithm for bandwidth of interval graphs. SIAM J. Discrete Math. 7, 213\u2013220 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"94_CR43","doi-asserted-by":"crossref","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"JB Tenenbaum","year":"2000","unstructured":"Tenenbaum, J.B., de Silva, V., Langford, J.C.: A global geometric framework for nonlinear dimensionality reduction. Science 290, 2319\u20132323 (2000)","journal-title":"Science"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0094-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0094-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0094-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0094-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T14:57:21Z","timestamp":1567349841000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0094-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,20]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["94"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0094-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,20]]}}}