{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T10:29:11Z","timestamp":1742984951208,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029264"},{"type":"electronic","value":"9783642029271"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02927-1_26","type":"book-chapter","created":{"date-parts":[[2009,7,4]],"date-time":"2009-07-04T04:37:10Z","timestamp":1246682230000},"page":"304-315","source":"Crossref","is-referenced-by-count":4,"title":["Exact and Approximate 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":"26_CR1","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion\u2013exclusion algorithms for counting set partitions. In: Proc. FOCS 2006, pp. 575\u2013582 (2006)","DOI":"10.1109\/FOCS.2006.41"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/1250790.1250801","volume-title":"STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"A. Bj\u00f6rklund","year":"2007","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 67\u201374. ACM Press, New York (2007)"},{"key":"26_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 (extended abstract). In: ACM Symposium on Theory of Computing, pp. 449\u2013458 (1994)","DOI":"10.1145\/195058.195229"},{"key":"26_CR4","unstructured":"Cygan, M., Pilipczuk, M.: Even faster exact bandwidth, arxiv:0902.1661v1 (unpublished, 2008), http:\/\/arxiv.org\/abs\/0902.1661v1"},{"key":"26_CR5","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":"26_CR6","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Heidelberg (2005)"},{"issue":"3","key":"26_CR7","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":"26_CR8","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":"26_CR9","unstructured":"Fomin, F.: Private communication (2009)"},{"key":"26_CR10","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":"26_CR11","doi-asserted-by":"crossref","unstructured":"Koivisto, M.: An O *(2 n ) algorithm for graph coloring and other partitioning problems via inclusion\u2013exclusion. In: Proc. FOCS 2006, pp. 583\u2013590 (2006)","DOI":"10.1109\/FOCS.2006.11"},{"key":"26_CR12","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":"26_CR13","unstructured":"Escoffier, B., Bourgeois, N., Paschos, V.T.: Efficient approximation by \u201clow-complexity\u201d exponential algorithms. Cahier du LAMSADE 271, LAMSADE, Universite Paris-Dauphine (2007)"},{"key":"26_CR14","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":"26_CR15","doi-asserted-by":"crossref","unstructured":"Unger, W.: The complexity of the approximation of the bandwidth problem. In: Proc. FOCS 1998, pp. 82\u201391 (1998)","DOI":"10.1109\/SFCS.1998.743431"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02927-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T02:53:45Z","timestamp":1558407225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02927-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029264","9783642029271"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02927-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}