{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:00:14Z","timestamp":1781078414999,"version":"3.54.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"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":[[2009,9]]},"DOI":"10.1007\/s00453-007-9002-0","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T13:56:40Z","timestamp":1192197400000},"page":"190-204","source":"Crossref","is-referenced-by-count":12,"title":["Approximating the Bandwidth of Caterpillars"],"prefix":"10.1007","volume":"55","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9002_CR1","unstructured":"Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem. Technical Report, University of Bonn (1997)"},{"issue":"3","key":"9002_CR2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P. Chinn","year":"1982","unstructured":"Chinn, P., Chvat\u00e1lov\u00e1, J., Dewdney, A., Gibbs, N.: The bandwidth problem for graphs and matrices\u2014survey. J. Graph. Theory 6(3), 223\u2013254 (1982)","journal-title":"J. Graph. Theory"},{"key":"9002_CR3","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0012-365X(89)90083-6","volume":"75","author":"F.R. Chung","year":"1989","unstructured":"Chung, F.R., Seymour, P.D.: Graphs with small bandwidth and cutwidth. Discret. Math. 75, 113\u2013119 (1989)","journal-title":"Discret. Math."},{"key":"9002_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-44666-4_26","volume-title":"RANDOM-APPROX","author":"J. Dunagan","year":"2001","unstructured":"Dunagan, J., Vempala, S.: On Euclidean embeddings and bandwidth minimization. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM-APPROX. Lecture Notes in Computer Science, vol. 2129, pp. 229\u2013240. Springer, New York (2001)"},{"issue":"3","key":"9002_CR5","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 embeddings. J. Comput. Syst. Sci. 60(3), 510\u2013539 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"9002_CR6","doi-asserted-by":"crossref","unstructured":"Feige, U.: Coping with the NP-hardness of the graph bandwidth problem. In: SWAT \u201900: Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, pp. 10\u201319 (2000)","DOI":"10.1007\/3-540-44985-X_2"},{"key":"9002_CR7","unstructured":"Filmus, Y.: Master\u2019s thesis, Weizmann Institute (2003)"},{"issue":"1","key":"9002_CR8","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(1), 24\u201336 (2001)","journal-title":"J. Algorithms"},{"key":"9002_CR9","doi-asserted-by":"crossref","unstructured":"Haralambides, J., Makedon, F., Monien, B.: Bandwidth minimization: An approximation algorithm for caterpillars. In: Mathematical Systems Theory, pp. 169\u2013177 (1991)","DOI":"10.1007\/BF02090396"},{"key":"9002_CR10","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. In: FOCS \u201904: Proceedings of the 45th Annual Symposium on Foundations of Computer Science, pp. 434\u2013443 (2004)","DOI":"10.1109\/FOCS.2004.41"},{"key":"9002_CR11","doi-asserted-by":"crossref","unstructured":"Monien, B.: The bandwidth minimization problem for caterpillars with hair length 3 is np-complete. SIAM J. Algebr. Discret. Method. 7(4) (1986)","DOI":"10.1137\/0607057"},{"key":"9002_CR12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1137\/0601042","volume":"1","author":"J. Saxe","year":"1980","unstructured":"Saxe, J.: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebr. Discret. Method. 1, 363\u2013369 (1980)","journal-title":"SIAM J. Algebr. Discret. Method."},{"key":"9002_CR13","doi-asserted-by":"crossref","unstructured":"Unger, W.: The complexity of the approximation of the bandwidth problem. In: FOCS \u201998: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p. 82 (1998)","DOI":"10.1109\/SFCS.1998.743431"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9002-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9002-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9002-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:44:59Z","timestamp":1559123099000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9002-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["9002"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9002-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}