{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T08:05:08Z","timestamp":1773475508645,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,16]],"date-time":"2016-11-16T00:00:00Z","timestamp":1479254400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"European Social Fund (ESF)"},{"name":"NSRF"},{"name":"ARISTEIA II"},{"name":"National Research Foundation of Korea (KR)","award":["2011-0011653"],"award-info":[{"award-number":["2011-0011653"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00453-016-0245-5","type":"journal-article","created":{"date-parts":[[2016,11,17]],"date-time":"2016-11-17T01:57:13Z","timestamp":1479347833000},"page":"116-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["An FPT 2-Approximation for Tree-Cut Decomposition"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6824-0516","authenticated-orcid":false,"given":"Eun Jung","family":"Kim","sequence":"first","affiliation":[]},{"given":"Sang-il","family":"Oum","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,16]]},"reference":[{"key":"245_CR1","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"245_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F., Lokshtanov, D., Pilipczuk, M.: A \n                        $$O(c^k n)$$\n                        \n                            \n                                \n                                    O\n                                    (\n                                    \n                                        c\n                                        k\n                                    \n                                    n\n                                    )\n                                \n                            \n                        \n                     5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"245_CR3","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms 21(2), 358\u2013402 (1996)","journal-title":"J. Algorithms"},{"key":"245_CR4","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Computing small search numbers in linear time. In: International Workshop on Parameterized and Exact Computation, IWPEC, volume 3162 of Lecture Notes in Computer Science, pp. 37\u201348 (2004)","DOI":"10.1007\/978-3-540-28639-4_4"},{"issue":"1","key":"245_CR5","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I: recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"245_CR6","unstructured":"Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and ptass. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u20192005), Vancouver, British Columbia, 23\u201325 Jan., 2005, pp. 590\u2013601 (2005)"},{"key":"245_CR7","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: International Workshop on Parameterized and Exact Computation, IWPEC, volume 5018 of Lecture Notes in Computer Science, pp. 78\u201390 (2008)","DOI":"10.1007\/978-3-540-79723-4_9"},{"issue":"2","key":"245_CR8","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"key":"245_CR9","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u20192011) San Francisco, 23\u201325 Jan., 2011, pp. 748\u2013759 (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"245_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA\u20192010) Austin, 17\u201319 Jan., 2010, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"245_CR11","doi-asserted-by":"crossref","unstructured":"Ganian, R., Kim, E.J., Szeider, S.: Algorithmic applications of tree-cut width. In: Proceedings, Part II Mathematical Foundations of Computer Science 2015: 40th International Symposium (MFCS\u20192015), Milan, 24\u201328 Aug., 2015, pp. 348\u2013360 (2015)","DOI":"10.1007\/978-3-662-48054-0_29"},{"key":"245_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness (1979)"},{"issue":"1","key":"245_CR13","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.disopt.2010.09.009","volume":"8","author":"PA Golovach","year":"2011","unstructured":"Golovach, P.A., Thilikos, D.M.: Paths of bounded length and their cuts: parameterized complexity and algorithms. Discrete Optim. 8(1), 72\u201386 (2011)","journal-title":"Discrete Optim."},{"key":"245_CR14","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In ACM Symposium on Theory of Computing, (STOC), pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"key":"245_CR15","doi-asserted-by":"crossref","unstructured":"Jeong, J., Kim, E.J., Oum, S.: Constructive algorithm for path-width of matroids. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA\u20192016), Arlington, 10\u201312 Jan., 2016, pp. 1695\u20131704 (2016)","DOI":"10.1137\/1.9781611974331.ch116"},{"key":"245_CR16","unstructured":"Kim, E.J., Oum, S., Paul, C., Sau, I., Thilikos, D.M.: An FPT 2-approximation for tree-cut decomposition. In: Approximation and Online Algorithms: 13th International Workshop, (WAOA\u20192015), Patras, 17\u201318 Sept., 2015. Revised Selected Papers, pp. 35\u201346 (2015)"},{"key":"245_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations, Volume 842 of LNCS","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations, Volume 842 of LNCS. Springer, Berlin (1994)"},{"issue":"1","key":"245_CR18","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III: planar tree-width. J. Combin. Theory, Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"1","key":"245_CR19","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. V: excluding a planar graph. J. Combin. Theory, Ser. B 41(1), 92\u2013114 (1986)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"2","key":"245_CR20","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jctb.2009.07.003","volume":"100","author":"N Robertson","year":"2010","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XXIII: Nash-Williams\u2019 immersion conjecture. J. Combin. Theory, Ser. B 100(2), 181\u2013205 (2010)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"1","key":"245_CR21","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"PD Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph searching and a min\u2013max theorem for tree-width. J. Combin. Theory, Ser. B 58(1), 22\u201333 (1993)","journal-title":"J. Combin. Theory, Ser. B"},{"issue":"2","key":"245_CR22","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"key":"245_CR23","unstructured":"Soares, R.P.: Pursuit-evasion, decompositions and convexity on graphs. Ph.D thesis, COATI, INRIA\/I3S-CNRS\/UNS Sophia Antipolis, France and ParGO Research Group, UFC Fortaleza (2014)"},{"issue":"1","key":"245_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: a linear time fixed parameter algorithm. J. Algorithms 56(1), 1\u201324 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"245_CR25","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jalgor.2004.12.003","volume":"56","author":"DM Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: algorithms for partial \n                        $$w$$\n                        \n                            \n                                w\n                            \n                        \n                    -trees of bounded degree. J. Algorithms 56(1), 25\u201349 (2005)","journal-title":"J. Algorithms"},{"key":"245_CR26","unstructured":"Watanabe, T., Taoka, S., Mashima, T.: Minimum-cost augmentation to 3-edge-connect all specified vertices in a graph. In: 1993 IEEE International Symposium on Circuits and Systems, (ISCAS\u20191993), Chicago, 3\u20136 May, 1993, pp. 2311\u20132314 (1993)"},{"key":"245_CR27","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.jctb.2014.07.003","volume":"110","author":"P Wollan","year":"2015","unstructured":"Wollan, P.: The structure of graphs not admitting a fixed immersion. J. Combin. Theory, Ser. B 110, 47\u201366 (2015)","journal-title":"J. Combin. Theory, Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0245-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0245-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0245-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,1,2]],"date-time":"2018-01-02T18:06:07Z","timestamp":1514916367000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0245-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,16]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["245"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0245-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,16]]}}}