{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T01:12:53Z","timestamp":1791421973676,"version":"4.3.3"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["Beating Hardness by Preprocessing"],"award-info":[{"award-number":["Beating Hardness by Preprocessing"]}],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["NETWORKS"],"award-info":[{"award-number":["NETWORKS"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>We give an algorithm that for an input $n$-vertex graph $G$ and integer $k&gt;0$, in time $2^{O(k)} n$, either outputs that the treewidth of $G$ is larger than $k$, or gives a tree decomposition of $G$ of width at most $5k+4$. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single exponential in $k$ and linear in $n$. Treewidth-based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single exponential in the treewidth and linear in the input size.<\/jats:p>","DOI":"10.1137\/130947374","type":"journal-article","created":{"date-parts":[[2016,3,31]],"date-time":"2016-03-31T13:07:07Z","timestamp":1459429627000},"page":"317-378","source":"Crossref","is-referenced-by-count":140,"title":["A $c^k n$ 5-Approximation Algorithm for Treewidth"],"prefix":"10.1137","volume":"45","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P\u00e5l Gr\u01ffn\u00e5s","family":"Drange","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Markus S.","family":"Dregi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,3,31]]},"reference":[{"key":"atypb1","first-page":"3","volume":"2012","author":"Abraham I.","year":"2012","journal-title":"EC"},{"key":"atypb2","first-page":"539","author":"Abrahamson K. R.","year":"1993","journal-title":"RI"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9180-4"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"P. Austrin, T. Pitassi, and Y. Wu,\n                      Inapproximability of treewidth, one-shot pebbling, and related layout problems\n                      , in Proceedings APPROX 2012 and RANDOM 2012, A. Gupta, K. Jansen, J. D. P. Rolim, and R. A. Servedio, eds., Lecture Notes in Comput. Sci. 7408, Springer Verlag, Berlin, 2012, pp. 13-24.","DOI":"10.1007\/978-3-642-32512-0_2"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender,\n                      Dynamic programming algorithms on graphs with bounded tree-width\n                      , in Proceedings of the 15th International Colloquium on Automata, Languages and Programming, ICALP'88, T. Lepist\u00f6 and A. Salomaa, eds., Lecture Notes in Comput. Sci. 317, Springer Verlag, Berlin, 1988, pp. 105-119.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"atypb7","first-page":"226","author":"Bodlaender H. L.","year":"1993","journal-title":"New York"},{"key":"atypb8","first-page":"112","author":"Bodlaender H. L.","year":"1994","journal-title":"Springer Verlag"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb11","first-page":"196","author":"Bodlaender H. L.","year":"2013","journal-title":"Berlin"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.027"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289859"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0049"},{"key":"atypb16","unstructured":"R. B. Borie,\n                      Recursively Constructed Graph Families\n                      , Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA, 1988."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00021-8"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010016"},{"key":"atypb19","first-page":"99","author":"Cohen R. F.","year":"1993","journal-title":"Belgium"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb21","first-page":"301","volume":"2013","author":"Cygan M.","year":"2013","journal-title":"STOC"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/1101821.1101823"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm033"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"M. Elberfeld, A. Jakoby, and T. Tantau,\n                      Logspace versions of the theorems of Bodlaender and Courcelle\n                      , in Proceedings of the 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 143-152.","DOI":"10.1109\/FOCS.2010.21"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"M. R. Fellows and M. A. Langston,\n                      An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations\n                      , in Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS'89, IEEE Computer Society, Los Alamitos, CA, 1989, pp. 520-525.","DOI":"10.1109\/SFCS.1989.63528"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00040"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Academic Press, New York, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010021"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"T. Kloks,\n                      Treewidth. Computations and Approximations\n                      , Lecture Notes in Comput. Sci. 842, Springer Verlag, Berlin, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1002\/net.10046"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0002"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"atypb35","first-page":"47","author":"Miller G. L.","year":"1989","journal-title":"CT"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/0220070"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000247"},{"key":"atypb38","first-page":"221","author":"Reed B.","year":"1992","journal-title":"New York"},{"key":"atypb39","first-page":"149","author":"Rinaudo P.","year":"2012","journal-title":"Heidelberg"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb42","unstructured":"J. E. Savage,\n                      Models of Computation-Exploring the Power of Computing\n                      , Addison-Wesley, Reading, MA, 1998."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194275825"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130947374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:32Z","timestamp":1787337992000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130947374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/130947374"],"URL":"https:\/\/doi.org\/10.1137\/130947374","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}