{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:26Z","timestamp":1781077706519,"version":"3.54.1"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PARAPPROX, ERC","award":["306992"],"award-info":[{"award-number":["306992"]}]},{"name":"European Research Council"},{"name":"European Union\u2019s Seventh Framework Programme","award":["FP\/2007-2013"],"award-info":[{"award-number":["FP\/2007-2013"]}]},{"name":"Foundation for Polish Science (FNP) via the START stipend program"},{"name":"ERC","award":["267959"],"award-info":[{"award-number":["267959"]}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2013\/11\/D\/ST6\/03073"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03073"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"name":"BeHard"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,7,31]]},"abstract":"<jats:p>\n            We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial time; however, the exponent of the polynomial is large. Therefore, our main goal is to construct algorithms with running time of the form poly(\n            <jats:italic>k<\/jats:italic>\n            )\u22c5\n            <jats:italic>n<\/jats:italic>\n            or poly(\n            <jats:italic>k<\/jats:italic>\n            )\u22c5\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            , where\n            <jats:italic>k<\/jats:italic>\n            is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1\/\n              <jats:italic>c<\/jats:italic>\n            <\/jats:sup>\n            ) for a constant\n            <jats:italic>c<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>Our results include the following:<\/jats:p>\n          <jats:p>\n            \u2014 an algorithm for computing the determinant and the rank of an\n            <jats:italic>n<\/jats:italic>\n            \u00d7\n            <jats:italic>n<\/jats:italic>\n            matrix using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            ) time and arithmetic operations;\n          <\/jats:p>\n          <jats:p>\n            \u2014an algorithm for solving a system of linear equations using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            ) time and arithmetic operations;\n          <\/jats:p>\n          <jats:p>\n            \u2014an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-time randomized algorithm for finding the cardinality of a maximum matching in a graph;\n          <\/jats:p>\n          <jats:p>\n            \u2014an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-time randomized algorithm for constructing a maximum matching in a graph;\n          <\/jats:p>\n          <jats:p>\n            \u2014an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm for finding a maximum vertex flow in a directed graph.\n          <\/jats:p>\n          <jats:p>\n            Moreover, we give an approximation algorithm for treewidth with time complexity suited to the running times as above. Namely, the algorithm, when given a graph\n            <jats:italic>G<\/jats:italic>\n            and integer\n            <jats:italic>k<\/jats:italic>\n            , runs in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>7<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) and either correctly reports that the treewidth of\n            <jats:italic>G<\/jats:italic>\n            is larger than\n            <jats:italic>k<\/jats:italic>\n            , or constructs a tree decomposition of\n            <jats:italic>G<\/jats:italic>\n            of width\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ).\n          <\/jats:p>\n          <jats:p>The above results stand in contrast with the recent work of Abboud et al.\u00a0(SODA 2016), which shows that the existence of algorithms with similar running times is unlikely for the problems of finding the diameter and the radius of a graph of low treewidth.<\/jats:p>","DOI":"10.1145\/3186898","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T12:28:11Z","timestamp":1529324891000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth"],"prefix":"10.1145","volume":"14","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"University of Bergen and Institute of Mathematical Sciences, HBNI, Taramani, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0141","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9346-2172","authenticated-orcid":false,"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,6,16]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Virginia Vassilevska Williams, and Joshua R. Wang","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud , Virginia Vassilevska Williams, and Joshua R. Wang . 2016 . Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In SODA 2016. SIAM , 377--391. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. 2016. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In SODA 2016. SIAM, 377--391."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508028.2505989"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118221.3118398"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022806215452"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646244.681623"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_5"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130947374"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1974-0331751-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00291"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_36"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00021-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010016"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/110844970"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_1_19_1","volume-title":"SODA","author":"Cohen Michael B.","year":"2017","unstructured":"Michael B. Cohen , Aleksander M\u0105dry , Piotr Sankowski , and Adrian Vladu . 2017. Negative-weight shortest paths and unit capacity minimum cost flow in \u00d5(m<sup>10\/7<\/sup> log W) time . In SODA 2017 . SIAM , 752--771. arXiv:1605.01717 Michael B. Cohen, Aleksander M\u0105dry, Piotr Sankowski, and Adrian Vladu. 2017. Negative-weight shortest paths and unit capacity minimum cost flow in \u00d5(m<sup>10\/7<\/sup> log W) time. In SODA 2017. SIAM, 752--771. arXiv:1605.01717"},{"key":"e_1_2_1_20_1","volume-title":"Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. CoRR","author":"Coudert David","year":"2017","unstructured":"David Coudert , Guillaume Ducoffe , and Alexandru Popa . 2017. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. CoRR ( 2017 ). arxiv:1707.05016http:\/\/arxiv.org\/abs\/1707.05016 David Coudert, Guillaume Ducoffe, and Alexandru Popa. 2017. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. CoRR (2017). arxiv:1707.05016http:\/\/arxiv.org\/abs\/1707.05016"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_22_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_23_1","volume-title":"IPEC 2016 (LIPIcs)","volume":"63","author":"Dell Holger","unstructured":"Holger Dell , Thore Husfeldt , Bart M. P. Jansen , Petteri Kaski , Christian Komusiewicz , and Frances A. Rosamond . 2017. The first parameterized algorithms and computational experiments challenge . In IPEC 2016 (LIPIcs) , Vol. 63 . 30:1--30:9. Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2017. The first parameterized algorithms and computational experiments challenge. In IPEC 2016 (LIPIcs), Vol. 63. 30:1--30:9."},{"key":"e_1_2_1_24_1","volume-title":"The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In IPEC 2017 (LIPIcs). 30:1--30:12","author":"Dell Holger","year":"2018","unstructured":"Holger Dell , Christian Komusiewicz , Nimrod Talmon , and Mathias Weller . 2018 . The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In IPEC 2017 (LIPIcs). 30:1--30:12 . Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. 2018. The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In IPEC 2017 (LIPIcs). 30:1--30:12."},{"key":"e_1_2_1_25_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in a network with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","unstructured":"E. A. Dinic . 1970 . Algorithm for solution of a problem of maximum flow in a network with power estimation . Soviet Math. Doklady 11 (1970), 1277 -- 1280 . http:\/\/www.cs.bgu.ac.il\/ dinitz\/D70.pdf. E. A. Dinic. 1970. Algorithm for solution of a problem of maximum flow in a network with power estimation. Soviet Math. Doklady 11 (1970), 1277--1280. http:\/\/www.cs.bgu.ac.il\/ dinitz\/D70.pdf.","journal-title":"Soviet Math. Doklady"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00149-3"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204043"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132573"},{"key":"e_1_2_1_32_1","volume-title":"Parameterized Complexity Theory","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory . Springer-Verlag , Berlin . 493 pages. J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag, Berlin. 493 pages."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039778"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/115234.115366"},{"key":"e_1_2_1_36_1","volume-title":"IPEC 2015 (LIPIcs)","volume":"43","author":"Giannopoulou Archontia C.","year":"2015","unstructured":"Archontia C. Giannopoulou , George B. Mertzios , and Rolf Niedermeier . 2015 . Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs . In IPEC 2015 (LIPIcs) , Vol. 43 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 102--113. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. 2015. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. In IPEC 2015 (LIPIcs), Vol. 43. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 102--113."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290181"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/646680.702325"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1592"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.8"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/070684008"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_44_1","volume-title":"On the power of tree-depth for fully polynomial FPT algorithms. CoRR","author":"Iwata Yoichi","year":"2017","unstructured":"Yoichi Iwata , Tomoaki Ogasawara , and Naoto Ohsaka . 2017. On the power of tree-depth for fully polynomial FPT algorithms. CoRR ( 2017 ). arxiv:1710.04376 http:\/\/arxiv.org\/abs\/1710.04376 Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2017. On the power of tree-depth for fully polynomial FPT algorithms. CoRR (2017). arxiv:1710.04376 http:\/\/arxiv.org\/abs\/1710.04376"},{"key":"e_1_2_1_45_1","first-page":"81","article-title":"O nakhozhdenii maksimal\u2019nogo potoka v setyakh spetsial\u2019nogo vida i nekotorykh prilozheniyakh","volume":"5","author":"Karzanov A. V.","year":"1973","unstructured":"A. V. Karzanov . 1973 . O nakhozhdenii maksimal\u2019nogo potoka v setyakh spetsial\u2019nogo vida i nekotorykh prilozheniyakh . Mat. Vopr. Upr, Proiz , 5 (1973), 81 -- 94 . In Russian. A. V. Karzanov. 1973. O nakhozhdenii maksimal\u2019nogo potoka v setyakh spetsial\u2019nogo vida i nekotorykh prilozheniyakh. Mat. Vopr. Upr, Proiz, 5 (1973), 81--94. In Russian.","journal-title":"Mat. Vopr. Upr, Proiz"},{"key":"e_1_2_1_46_1","volume-title":"Lorenzo Orecchia, and Aaron Sidford.","author":"Kelner Jonathan A.","year":"2014","unstructured":"Jonathan A. Kelner , Yin Tat Lee , Lorenzo Orecchia, and Aaron Sidford. 2014 . An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In SODA 2014. SIAM , 217--226. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. 2014. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In SODA 2014. SIAM, 217--226."},{"key":"e_1_2_1_47_1","volume-title":"Algorithm Design","author":"Kleinberg Jon M.","unstructured":"Jon M. Kleinberg and \u00c9va Tardos . 2006. Algorithm Design . Addison-Wesley . Jon M. Kleinberg and \u00c9va Tardos. 2006. Algorithm Design. Addison-Wesley."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488704"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/0716027"},{"key":"e_1_2_1_51_1","volume-title":"Fundamentals of Computation Theory","author":"Lov\u00e1sz L\u00e1szl\u00f3","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1979. On determinants, matchings, and random algorithms . In Fundamentals of Computation Theory . Akademie Verlag , 565--574. L\u00e1szl\u00f3 Lov\u00e1sz. 1979. On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory. Akademie Verlag, 565--574."},{"key":"e_1_2_1_52_1","volume-title":"MFCS","author":"Mertzios George B.","year":"2017","unstructured":"George B. Mertzios , Andr\u00e9 Nichterlein , and Rolf Niedermeier . 2017 . The power of linear-time data reduction for maximum matching . In MFCS 2017. 46:1--46:14. George B. Mertzios, Andr\u00e9 Nichterlein, and Rolf Niedermeier. 2017. The power of linear-time data reduction for maximum matching. In MFCS 2017. 46:1--46:14."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.70"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-005-1187-5"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1003021"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884565"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387915.2387925"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90005-9"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/646508.694498"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129734"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.36"},{"key":"e_1_2_1_67_1","volume-title":"Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR abs\/1709.08949","author":"Strasser Ben","year":"2017","unstructured":"Ben Strasser . 2017. Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR abs\/1709.08949 ( 2017 ). arxiv:1709.08949 http:\/\/arxiv.org\/abs\/1709.08949 Ben Strasser. 2017. Computing tree decompositions with flowcutter: PACE 2017 submission. CoRR abs\/1709.08949 (2017). arxiv:1709.08949 http:\/\/arxiv.org\/abs\/1709.08949"},{"key":"e_1_2_1_68_1","volume-title":"ESA","author":"Tamaki Hisao","year":"2017","unstructured":"Hisao Tamaki . 2017 . Positive-instance driven dynamic programming for treewidth . In ESA 2017. 68:1--68:13. Hisao Tamaki. 2017. Positive-instance driven dynamic programming for treewidth. In ESA 2017. 68:1--68:13."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-22.2.107"},{"key":"e_1_2_1_71_1","volume-title":"Bodlaender","author":"van der Zanden Tom C.","year":"2017","unstructured":"Tom C. van der Zanden and Hans L . Bodlaender . 2017 . Computing treewidth on the GPU. CoRR ( 2017). arxiv:1709.09990 http:\/\/arxiv.org\/abs\/1709.09990 Tom C. van der Zanden and Hans L. Bodlaender. 2017. Computing treewidth on the GPU. CoRR (2017). arxiv:1709.09990 http:\/\/arxiv.org\/abs\/1709.09990"},{"key":"e_1_2_1_72_1","unstructured":"Vijay V. Vazirani. 2014. A proof of the MV matching algorithm.  Vijay V. Vazirani. 2014. A proof of the MV matching algorithm."},{"key":"e_1_2_1_73_1","volume-title":"Shmoys","author":"Williamson David P.","year":"2011","unstructured":"David P. Williamson and David B . Shmoys . 2011 . The Design of Approximation Algorithms. Cambridge University Press . David P. Williamson and David B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press."},{"key":"e_1_2_1_74_1","volume-title":"SODA","author":"Wilson David Bruce","year":"1997","unstructured":"David Bruce Wilson . 1997. Determinant algorithms for random planar structures . In SODA 1997 . ACM\/SIAM , 258--267. David Bruce Wilson. 1997. Determinant algorithms for random planar structures. In SODA 1997. ACM\/SIAM, 258--267."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.010"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.5555\/2655713.2655729"},{"key":"e_1_2_1_77_1","volume-title":"SODA","author":"Yuster Raphael","year":"2007","unstructured":"Raphael Yuster and Uri Zwick . 2007. Maximum matching in graphs with an excluded minor . In SODA 2007 . SIAM , 108--117. Raphael Yuster and Uri Zwick. 2007. Maximum matching in graphs with an excluded minor. In SODA 2007. SIAM, 108--117."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:32Z","timestamp":1750273652000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,16]]},"references-count":77,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,7,31]]}},"alternative-id":["10.1145\/3186898"],"URL":"https:\/\/doi.org\/10.1145\/3186898","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,16]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}