{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:30:07Z","timestamp":1742931007664,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_14","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"173-184","source":"Crossref","is-referenced-by-count":11,"title":["An Exponential Time 2-Approximation Algorithm for Bandwidth"],"prefix":"10.1007","author":[{"given":"Martin","family":"F\u00fcrer","sequence":"first","affiliation":[]},{"given":"Serge","family":"Gaspers","sequence":"additional","affiliation":[]},{"given":"Shiva Prasad","family":"Kasiviswanathan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Counting Subgraphs via Homomorphisms. In: Proceedings of ICALP 2009, pp. 71\u201382 (2009)","DOI":"10.1007\/978-3-642-02927-1_8"},{"issue":"1","key":"14_CR2","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0304-3975(99)00181-4","volume":"235","author":"A. Blum","year":"2000","unstructured":"Blum, A., Konjevod, G., Ravi, R., Vempala, S.: Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems. Theor. Comput. Sci.\u00a0235(1), 25\u201342 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.T.: Beyond NP-completeness for Problems of Bounded Width: Hardness for the W-hierarchy. In: Proceedings of STOC 1994, pp. 449\u2013458 (1994)","DOI":"10.1145\/195058.195229"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Linear FPT Reductions and Computational Lower Bounds. In: Proceedings of STOC 2004, pp. 212\u2013221 (2004)","DOI":"10.1145\/1007352.1007391"},{"key":"14_CR5","unstructured":"Cygan, M., Kowalik, L., Pilipczuk, M., Wykurz, M.: Exponential-time Approximation of Hard Problems, Technical Report abs\/0810.4934, arXiv, CoRR (2008)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-540-92248-3_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M. Cygan","year":"2008","unstructured":"Cygan, M., Pilipczuk, M.: Faster exact bandwidth. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 101\u2013109. Springer, Heidelberg (2008)"},{"key":"14_CR7","unstructured":"Cygan, M., Pilipczuk, M.: Even Faster Exact Bandwidth, Technical Report abs\/0902.1661, arXiv, CoRR (2009)"},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Cygan, M., Pilipczuk, M.: Exact and approximate Bandwidth. In: Proceedings of ICALP 2009, pp. 304\u2013315 (2009)","DOI":"10.1007\/978-3-642-02927-1_26"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/3-540-44666-4_26","volume-title":"Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques","author":"J. Dunagan","year":"2001","unstructured":"Dunagan, J., Vempala, S.S.: On euclidean embeddings and bandwidth minimization. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM 2001 and APPROX 2001. LNCS, vol.\u00a02129, pp. 229\u2013240. Springer, Heidelberg (2001)"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","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.\u00a060(3), 510\u2013539 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/3-540-44985-X_2","volume-title":"Algorithm Theory - SWAT 2000","author":"U. Feige","year":"2000","unstructured":"Feige, U.: Coping with the NP-Hardness of the Graph Bandwidth Problem. In: Halld\u00f3rsson, M.M. (ed.) SWAT 2000. LNCS, vol.\u00a01851, pp. 10\u201319. Springer, Heidelberg (2000)"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/11538462_6","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"U. Feige","year":"2005","unstructured":"Feige, U., Talwar, K.: Approximating the bandwidth of caterpillars. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 62\u201373. Springer, Heidelberg (2005)"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., Gaspers, S., Kasiviswanathan, S.P.: An Exponential Time 2-Approximation Algorithm for Bandwidth, Technical Report abs\/0906.1953, arXiv, CoRR (2009)","DOI":"10.1007\/978-3-642-11269-0_14"},{"issue":"3","key":"14_CR14","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity Results for Bandwidth Minimization. SIAM J. Appl. Math.\u00a034(3), 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the Complexity of k-SAT. J. Comput. Syst. Sci.\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"14_CR16","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1007\/s00454-009-9135-9","volume":"41","author":"J.R. Lee","year":"2009","unstructured":"Lee, J.R.: Volume Distortion for subsets of Euclidean Spaces. Discrete Comput. Geom.\u00a041(4), 590\u2013615 (2009)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"14_CR17","doi-asserted-by":"publisher","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. Alg. Disc. Meth.\u00a07(4), 505\u2013512 (1986)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"14_CR18","unstructured":"Monien, B., Sudborough, I.H.: Bandwidth Problems in Graphs. In: Proceedings of Allerton Conference on Communication, Control, and Computing 1980, pp. 650\u2013659 (1980)"},{"key":"14_CR19","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.: The NP-completeness of the Bandwidth Minimization Problem. Computing\u00a016, 263\u2013270 (1976)","journal-title":"Computing"},{"key":"14_CR20","doi-asserted-by":"publisher","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. Alg. Disc. Meth.\u00a01, 363\u2013369 (1980)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Unger, W.: The Complexity of the Approximation of the Bandwidth Problem. In: Proceedings of FOCS 1998, pp. 82\u201391 (1998)","DOI":"10.1109\/SFCS.1998.743431"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Vassilevska, V., Williams, R., Woo, S.L.M.: Confronting Hardness using a Hybrid Approach. In: Proceedings of SODA 2006, pp. 1\u201310 (2006)","DOI":"10.1145\/1109557.1109558"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T14:46:15Z","timestamp":1739457975000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}