{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:18:41Z","timestamp":1781259521029,"version":"3.54.1"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish Ministry of Science and Higher Education","award":["N206 005 32\/0807"],"award-info":[{"award-number":["N206 005 32\/0807"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,1]]},"abstract":"\n We deal with exact algorithms for\n Bandwidth<\/jats:sc>\n , a long studied NP-hard problem. For a long time nothing better than the trivial\n O<\/jats:italic>\n *<\/jats:sup>\n (\n n<\/jats:italic>\n !)\n 1<\/jats:sup>\n exhaustive search was known. In 2000, Feige and Kilian [Feige 2000] came up with a\n O<\/jats:italic>\n *<\/jats:sup>\n (10\n n<\/jats:italic>\n )-time and polynomial space algorithm.\n <\/jats:p>\n \n In this article we present a new algorithm that solves\n Bandwidth<\/jats:sc>\n in\n O<\/jats:italic>\n *<\/jats:sup>\n (5\n n<\/jats:italic>\n ) time and\n O<\/jats:italic>\n *<\/jats:sup>\n (2\n n<\/jats:italic>\n ) space. Then, we take a closer look and introduce a major modification that makes it run in\n O<\/jats:italic>\n (4.83\n n<\/jats:italic>\n ) time with a cost of a\n O<\/jats:italic>\n *<\/jats:sup>\n (4\n n<\/jats:italic>\n ) space complexity. This modification allowed us to perform the Measure & Conquer analysis for the time complexity which was not used for graph layout problems before.\n <\/jats:p>","DOI":"10.1145\/2071379.2071387","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Even Faster Exact Bandwidth"],"prefix":"10.1145","volume":"8","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"University of Warsaw"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0602041"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195229"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Workshop on Graph-Theoretic Concept in Computer Science (WG\u201908)","author":"Cygan M.","unstructured":"Cygan , M. and Pilipczuk , M . 2008. Faster exact bandwidth . In Proceedings of the International Workshop on Graph-Theoretic Concept in Computer Science (WG\u201908) . 101--109. Cygan, M. and Pilipczuk, M. 2008. Faster exact bandwidth. In Proceedings of the International Workshop on Graph-Theoretic Concept in Computer Science (WG\u201908). 101--109."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645900.672601"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_16"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1552285.1552286"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0134037"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403033"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9135-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0607057"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796465"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071387","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071379.2071387","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071387"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071379.2071387"],"URL":"https:\/\/doi.org\/10.1145\/2071379.2071387","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}