{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T04:03:13Z","timestamp":1748836993469,"version":"3.41.0"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286839"},{"type":"electronic","value":"9783319286846"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-28684-6_4","type":"book-chapter","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T10:32:03Z","timestamp":1452594723000},"page":"35-46","source":"Crossref","is-referenced-by-count":5,"title":["An FPT 2-Approximation for Tree-cut Decomposition"],"prefix":"10.1007","author":[{"given":"Eunjung","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,1,13]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","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."},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F., Lokshtanov, D., Pilipczuk, M.: An $$O(c^k n)$$ O ( c k n ) $$5$$ 5 -approximation algorithm for treewidth. In: IEEE Symposium on Foundations of Computer Science, FOCS, pp. 499\u2013508 (2013)","DOI":"10.1109\/FOCS.2013.60"},{"issue":"2","key":"4_CR3","doi-asserted-by":"publisher","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":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-540-28639-4_4","volume-title":"Parameterized and Exact Computation","author":"HL Bodlaender","year":"2004","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Computing small search numbers in linear time. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 37\u201348. Springer, Heidelberg (2004)"},{"issue":"1","key":"4_CR5","doi-asserted-by":"publisher","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":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-79723-4_9","volume-title":"Parameterized and Exact Computation","author":"M Dom","year":"2008","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S., Villanger, Y.: Capacitated domination and covering: a parameterized perspective. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 78\u201390. Springer, Heidelberg (2008)"},{"issue":"2","key":"4_CR7","doi-asserted-by":"publisher","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":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-662-48054-0_29","volume-title":"Mathematical Foundations of Computer Science 2015","author":"R Ganian","year":"2015","unstructured":"Ganian, R., Kim, E.J., Szeider, S.: Algorithmic applications of tree-cut width. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 348\u2013360. Springer, Heidelberg (2015)"},{"key":"4_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"1","key":"4_CR10","doi-asserted-by":"publisher","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":"4_CR11","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":"4_CR12","unstructured":"Jeong, J., Kim, E.J., Oum, S.: Constructive algorithm for path-width of matroids. CoRR (2015). arXiv:1507.02184"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994)"},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","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. Comb. Theory Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"4_CR15","doi-asserted-by":"publisher","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. Comb. Theory Ser. B 41(1), 92\u2013114 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"4_CR16","doi-asserted-by":"publisher","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. Comb. Theory Ser. B 100(2), 181\u2013205 (2010)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"4_CR17","doi-asserted-by":"publisher","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-max theorem for tree-width. J. Comb. Theory Ser. B 58(1), 22\u201333 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"4_CR18","doi-asserted-by":"publisher","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":"4_CR19","unstructured":"Soares, R.P.: Pursuit-evasion, decompositions and convexity on graphs. PhD thesis, COATI, INRIA\/I3S-CNRS\/UNS Sophia Antipolis, France and ParGO Research Group, UFC Fortaleza, Brazil (2014)"},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","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":"4_CR21","doi-asserted-by":"publisher","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 $$w$$ w -trees of bounded degree. J. Algorithms 56(1), 25\u201349 (2005)","journal-title":"J. Algorithms"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Watanabe, T., Taoka, S., Mashima, T.: Minimum-cost augmentation to 3-edge-connect all specified vertices in a graph. In: ISCAS, pp. 2311\u20132314 (1993)","DOI":"10.1109\/ISCAS.1993.394225"},{"key":"4_CR23","doi-asserted-by":"publisher","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. Comb. Theory Ser. B 110, 47\u201366 (2015)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28684-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T03:25:27Z","timestamp":1748748327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28684-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319286839","9783319286846"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28684-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}