{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:37:56Z","timestamp":1777549076102,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540922476","type":"print"},{"value":"9783540922483","type":"electronic"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-92248-3_10","type":"book-chapter","created":{"date-parts":[[2008,12,4]],"date-time":"2008-12-04T08:36:17Z","timestamp":1228379777000},"page":"101-109","source":"Crossref","is-referenced-by-count":14,"title":["Faster Exact Bandwidth"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"S. Assman","year":"1981","unstructured":"Assman, S., Peck, G., Syslo, M., Zak, J.: The bandwidth of caterpillars with hairs of length 1 and 2. SIAM J. Algebraic Discrete Methods\u00a02, 387\u2013393 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10_CR2","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 (extended abstract). ACM Symposium on Theory of Computing, 449\u2013458 (1994)","DOI":"10.1145\/195058.195229"},{"issue":"3","key":"10_CR3","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":"10_CR4","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":"10_CR5","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. Garey","year":"1978","unstructured":"Garey, M., Graham, R., Johnson, D., Knuth, D.: Complexity results for bandwidth minimization. SIAM J. Appl. Math.\u00a034, 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0403033","volume":"3","author":"D. Kleitman","year":"1990","unstructured":"Kleitman, D., Vohra, R.: Computing the bandwidth of interval graphs. SIAM J. Discrete Math.\u00a03, 373\u2013375 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"10_CR7","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 hairlength 3 is np-complete. SIAM J. Algebraic Discrete Methods\u00a07, 505\u2013512 (1986)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10_CR8","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 Journal on Algebraic Methods\u00a01, 363\u2013369 (1980)","journal-title":"SIAM Journal on Algebraic Methods"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Unger, W.: The complexity of the approximation of the bandwidth problem. In: FOCS, pp. 82\u201391 (1998)","DOI":"10.1109\/SFCS.1998.743431"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92248-3_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,4]],"date-time":"2019-03-04T03:14:42Z","timestamp":1551669282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92248-3_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922476","9783540922483"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92248-3_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008]]}}}