{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T13:20:48Z","timestamp":1725974448669},"reference-count":19,"publisher":"Elsevier BV","issue":"40-42","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2014,9,6]],"date-time":"2014-09-06T00:00:00Z","timestamp":1409961600000},"content-version":"vor","delay-in-days":1466,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2010,9]]},"DOI":"10.1016\/j.tcs.2010.06.018","type":"journal-article","created":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T04:41:01Z","timestamp":1277959261000},"page":"3701-3713","source":"Crossref","is-referenced-by-count":46,"title":["Exact and approximate bandwidth"],"prefix":"10.1016","volume":"411","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2010.06.018_br000005","series-title":"Proc. ICALP\u201909 (1)","first-page":"304","article-title":"Exact and Approximate Bandwidth","volume":"vol. 5555","author":"Cygan","year":"2009"},{"key":"10.1016\/j.tcs.2010.06.018_br000010","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","article-title":"Complexity results for bandwidth minimization","volume":"34","author":"Garey","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/j.tcs.2010.06.018_br000015","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0607057","article-title":"The bandwidth-minimization problem for caterpillars with hairlength 3 is NP-complete","volume":"7","author":"Monien","year":"1986","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"10.1016\/j.tcs.2010.06.018_br000020","doi-asserted-by":"crossref","unstructured":"W. Unger, The complexity of the approximation of the bandwidth problem, in: Proc. FOCS\u201998, 1998, pp. 82\u201391.","DOI":"10.1109\/SFCS.1998.743431"},{"key":"10.1016\/j.tcs.2010.06.018_br000025","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, M.R. Fellows, M.T. Hallett, Beyond NP-completeness for problems of bounded width: hardness for the W Hierarchy (Extended Abstract), in: Proc. STOC\u201994, 1994, pp. 449\u2013458.","DOI":"10.1145\/195058.195229"},{"key":"10.1016\/j.tcs.2010.06.018_br000030","series-title":"Proc. RANDOM-APPROX\u201901","first-page":"229","article-title":"On euclidean embeddings and bandwidth minimization","volume":"vol. 2129","author":"Dunagan","year":"2001"},{"issue":"1","key":"10.1016\/j.tcs.2010.06.018_br000035","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/s00453-007-9002-0","article-title":"Approximating the bandwidth of caterpillars","volume":"55","author":"Feige","year":"2009","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2010.06.018_br000040","series-title":"Proc. WG\u201908","first-page":"101","article-title":"Faster exact bandwidth","volume":"vol. 5344","author":"Cygan","year":"2008"},{"key":"10.1016\/j.tcs.2010.06.018_br000045","doi-asserted-by":"crossref","unstructured":"M. Cygan, M. Pilipczuk, Even faster exact bandwidth, ACM Trans. Algorithms (in press).","DOI":"10.1145\/2071379.2071387"},{"key":"10.1016\/j.tcs.2010.06.018_br000050","series-title":"Proc. SWAT\u201900","first-page":"10","article-title":"Coping with the NP-hardness of the graph bandwidth problem","volume":"vol. 1851","author":"Feige","year":"2000"},{"key":"10.1016\/j.tcs.2010.06.018_br000055","series-title":"Proc. IWPEC\u201909","first-page":"173","article-title":"An Exponential time 2-approximation algorithm for bandwidth","volume":"vol. 5917","author":"F\u00fcrer","year":"2009"},{"key":"10.1016\/j.tcs.2010.06.018_br000060","series-title":"Proc. ICALP\u201909 (1)","first-page":"71","article-title":"Counting subgraphs via homomorphisms","volume":"vol. 5555","author":"Amini","year":"2009"},{"key":"10.1016\/j.tcs.2010.06.018_br000065","series-title":"Proc. WADS\u201909","article-title":"Efficient approximation of combinatorial problems by moderately exponential algorithms","volume":"vol. 5664","author":"Bourgeois","year":"2009"},{"key":"10.1016\/j.tcs.2010.06.018_br000070","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, P. Kaski, M. Koivisto, Fourier meets m\u00f6bius: fast subset convolution, in: Proc. STOC\u201907, 2007, pp. 67\u201374.","DOI":"10.1145\/1250790.1250801"},{"key":"10.1016\/j.tcs.2010.06.018_br000075","series-title":"Graph Theory","author":"Diestel","year":"2005"},{"key":"10.1016\/j.tcs.2010.06.018_br000080","doi-asserted-by":"crossref","unstructured":"R.T. Moenck, Practical fast polynomial multiplication, in: Proc. SYMSAC\u201976, 1976, pp. 136\u2013148.","DOI":"10.1145\/800205.806332"},{"key":"10.1016\/j.tcs.2010.06.018_br000085","doi-asserted-by":"crossref","unstructured":"A. Bj\u00f6rklund, T. Husfeldt, Inclusion\u2013exclusion algorithms for counting set partitions, in: Proc. FOCS\u201906, 2006, pp. 575\u2013582.","DOI":"10.1109\/FOCS.2006.41"},{"key":"10.1016\/j.tcs.2010.06.018_br000090","doi-asserted-by":"crossref","unstructured":"M. Koivisto, An O\u2217(2n) algorithm for graph coloring and other partitioning problems via inclusion\u2013exclusion, in: Proc. FOCS\u201906, 2006, pp. 583\u2013590.","DOI":"10.1109\/FOCS.2006.11"},{"key":"10.1016\/j.tcs.2010.06.018_br000095","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebr. Discrete Methods"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439751000352X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439751000352X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T12:45:03Z","timestamp":1559220303000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439751000352X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":19,"journal-issue":{"issue":"40-42","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["S030439751000352X"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2010.06.018","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}