{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:40:42Z","timestamp":1740109242828,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T00:00:00Z","timestamp":1477008000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea (KR)","doi-asserted-by":"publisher","award":["2011-0011653"],"award-info":[{"award-number":["2011-0011653"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002887","name":"Conseil R\u00e9gional Languedoc-Roussillon","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002887","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-016-0230-z","type":"journal-article","created":{"date-parts":[[2016,10,21]],"date-time":"2016-10-21T11:21:16Z","timestamp":1477048876000},"page":"66-95","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An FPT Algorithm and a Polynomial Kernel for Linear Rankwidth-1 Vertex Deletion"],"prefix":"10.1007","volume":"79","author":[{"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"first","affiliation":[]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,21]]},"reference":[{"key":"230_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.dam.2013.05.001","volume":"168","author":"I Adler","year":"2014","unstructured":"Adler, I., Farley, A.M., Proskurowski, A.: Obstructions for linear rank-width at most 1. Discrete Appl. Math. 168, 3\u201313 (2014)","journal-title":"Discrete Appl. Math."},{"key":"230_CR2","unstructured":"Adler, I., Kant\u00e9, M.M., Kwon, O.: Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions. preprint (2015). arXiv:1508.04718"},{"key":"230_CR3","doi-asserted-by":"publisher","unstructured":"Adler, I., Kant\u00e9, M.M., Kwon, O.: Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm. Algorithmica (2016). doi: 10.1007\/s00453-016-0164-5","DOI":"10.1007\/s00453-016-0164-5"},{"issue":"2","key":"230_CR4","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H-J Bandelt","year":"1986","unstructured":"Bandelt, H.-J., Mulder, H.M.: Distance-hereditary graphs. J. Comb. Theory Ser. B 41(2), 182\u2013208 (1986)","journal-title":"J. Comb. Theory Ser. B"},{"key":"230_CR5","unstructured":"Bui-Xuan, B., Kant\u00e9, M.M., Limouzy, V.: A note on graphs of linear rank-width 1. preprint (2013). arXiv:1306.1345"},{"issue":"4","key":"230_CR6","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L Cai","year":"2003","unstructured":"Cai, L., Juedes, D.: On the existence of subexponential parameterized algorithms. J. Comput. Syst. Sci. 67(4), 789\u2013807 (2003). (Special issue on parameterized computation and complexity)","journal-title":"J. Comput. Syst. Sci."},{"key":"230_CR7","doi-asserted-by":"crossref","unstructured":"Cao, Y.: Unit interval editing is fixed-parameter tractable. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming. Part I, Volume 9134 of Lecture Notes in Computer Science, pp. 306\u2013317. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-47672-7_25"},{"key":"230_CR8","doi-asserted-by":"crossref","unstructured":"Cao, Y., Marx, D.: Interval deletion is fixed-parameter tractable. ACM Trans. Algorithms 11(3), Art. 21, 35 (2015)","DOI":"10.1145\/2629595"},{"key":"230_CR9","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. In: Studies in Integer Programming, Annals of Discrete Mathematics (Proceedings Workshop, Bonn, 1975), vol. 1, pp. 145\u2013162. North-Holland, Amsterdam (1977)","DOI":"10.1016\/S0167-5060(08)70731-3"},{"issue":"1","key":"230_CR10","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."},{"issue":"4","key":"230_CR11","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1016\/j.dam.2008.08.026","volume":"157","author":"B Courcelle","year":"2009","unstructured":"Courcelle, B., Kant\u00e9, M.M.: Graph operations characterizing rank-width. Discrete Appl. Math. 157(4), 627\u2013640 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"230_CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"230_CR13","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jctb.2006.04.003","volume":"97","author":"B Courcelle","year":"2007","unstructured":"Courcelle, B., Oum, S.: Vertex-minors, monadic second-order logic, and a conjecture by Seese. J. Comb. Theory Ser. B 97(1), 91\u2013126 (2007)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"230_CR14","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebraic Discrete Methods 3(2), 214\u2013228 (1982)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"230_CR15","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/s00453-011-9578-2","volume":"64","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. Algorithmica 64(1), 170\u2013188 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"230_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2000.1090","volume":"36","author":"E Dahlhaus","year":"2000","unstructured":"Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. J. Algorithms 36(2), 205\u2013240 (2000)","journal-title":"J. Algorithms"},{"key":"230_CR17","unstructured":"Eiben, E., Ganian, R., Kwon, O.: A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Volume 58 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 1\u201334. Dagstuhl, Germany (2016)"},{"key":"230_CR18","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-Deletion: approximation, kernelization and optimal FPT algorithms. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science-FOCS 2012, pp. 470\u2013479. IEEE Computer Society, Los Alamitos, CA (2012)","DOI":"10.1109\/FOCS.2012.62"},{"issue":"4","key":"230_CR19","doi-asserted-by":"crossref","first-page":"1964","DOI":"10.1137\/12089051X","volume":"27","author":"FV Fomin","year":"2013","unstructured":"Fomin, F.V., Saurabh, S., Villanger, Y.: A polynomial kernel for proper interval vertex deletion. SIAM J. Discrete Math. 27(4), 1964\u20131976 (2013)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20133","key":"230_CR20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.apal.2004.01.007","volume":"130","author":"M Frick","year":"2004","unstructured":"Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1\u20133), 3\u201331 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"key":"230_CR21","doi-asserted-by":"crossref","unstructured":"Ganian, R.: Thread graphs, linear rank-width and their algorithmic applications. In: Iliopoulos, C.S., Smyth, W.F. (eds.) Combinatorial Algorithms, Volume 6460 of Lecture Notes in Computer Science, pp. 38\u201342. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-19222-7_5"},{"issue":"7","key":"230_CR22","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1016\/j.dam.2009.10.018","volume":"158","author":"R Ganian","year":"2010","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P.: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Appl. Math. 158(7), 851\u2013867 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"230_CR23","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/j.jctb.2005.09.005","volume":"96","author":"J Geelen","year":"2006","unstructured":"Geelen, J., Gerards, B., Whittle, G.: On Rota\u2019s conjecture and excluded minors containing large projective geometries. J. Comb. Theory Ser. B 96(3), 405\u2013425 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"230_CR24","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1016\/j.dam.2011.05.007","volume":"160","author":"E Gioan","year":"2012","unstructured":"Gioan, E., Paul, C.: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs. Discrete Appl. Math. 160(6), 708\u2013733 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"230_CR25","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1016\/j.ejc.2005.10.005","volume":"28","author":"R Hall","year":"2007","unstructured":"Hall, R., Oxley, J., Semple, C.: The structure of 3-connected matroids of path width three. Eur. J. Comb. 28(3), 964\u2013989 (2007)","journal-title":"Eur. J. Comb."},{"issue":"4","key":"230_CR26","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). Special issue on FOCS 98. Palo Alto, CA","journal-title":"J. Comput. Syst. Sci."},{"key":"230_CR27","doi-asserted-by":"crossref","unstructured":"Jeong, J., Kim, E.J., Oum, S.: Constructive algorithm for path-width of matroids. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1695\u20131704. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch116"},{"key":"230_CR28","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1016\/j.ejc.2014.04.010","volume":"41","author":"J Jeong","year":"2014","unstructured":"Jeong, J., Kwon, O., Oum, S.: Excluded vertex-minors for graphs of linear rank-width at most $$k$$ k . Eur. J. Comb. 41, 242\u2013257 (2014)","journal-title":"Eur. J. Comb."},{"issue":"8","key":"230_CR29","doi-asserted-by":"crossref","first-page":"1820","DOI":"10.1016\/j.ejc.2012.03.034","volume":"33","author":"MM Kant\u00e9","year":"2012","unstructured":"Kant\u00e9, M.M.: Well-quasi-ordering of matrices under Schur complement and applications to directed graphs. Eur. J. Comb. 33(8), 1820\u20131841 (2012)","journal-title":"Eur. J. Comb."},{"key":"230_CR30","unstructured":"Kant\u00e9, M.M., Kim, E.J., Kwon, O.-J., Paul, C.: An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion. In: 10th International Symposium on Parameterized and Exact Computation, Volume-43 of LIPIcs. Leibniz International Proceedings in Informatics, pp. 138\u2013150. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2015)"},{"issue":"1","key":"230_CR31","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1137\/070691152","volume":"22","author":"N Kashyap","year":"2008","unstructured":"Kashyap, N.: Matroid pathwidth and code trellis complexity. SIAM J. Discrete Math. 22(1), 256\u2013272 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"230_CR32","doi-asserted-by":"crossref","unstructured":"Kim, E.J., Langer, A., Paul, C., Reidl, F., Rossmanith, P., Sau, I., Sikdar, S.: Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms 12(2), Art. 21, 41 (2016)","DOI":"10.1145\/2797140"},{"key":"230_CR33","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.disc.2013.10.007","volume":"315","author":"A Koutsonas","year":"2014","unstructured":"Koutsonas, A., Thilikos, D.M., Yamazaki, K.: Outerplanar obstructions for matroid pathwidth. Discrete Math. 315, 95\u2013101 (2014)","journal-title":"Discrete Math."},{"key":"230_CR34","unstructured":"Li, W., Yang, Y., Chen, J., Wang, J.: Further Kernelization of Proper Interval Vertex Deletion: New Observations and Refined Analysis. preprint (2016). arXiv:1606.01925"},{"issue":"1","key":"230_CR35","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"key":"230_CR36","doi-asserted-by":"crossref","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5(1), Art. 10, 20 (2008)","DOI":"10.1145\/1435375.1435385"},{"issue":"4","key":"230_CR37","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory Ser. B"},{"key":"230_CR38","first-page":"196","volume-title":"Graph Theoretic Concepts in Computer Science, Volume 6410 of Lecture Notes in Computer Science","author":"G Philip","year":"2010","unstructured":"Philip, G., Raman, V., Villanger, Y.: A quartic kernel for pathwidth-one vertex deletion. In: Thilikos, D. (ed.) Graph Theoretic Concepts in Computer Science, Volume 6410 of Lecture Notes in Computer Science, pp. 196\u2013207. Springer, Berlin, Heidelberg (2010)"},{"issue":"2","key":"230_CR39","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"230_CR40","doi-asserted-by":"crossref","unstructured":"van Bevern, R., Komusiewicz, C., Moser, H., Niedermeier, R.: Measuring indifference: unit interval vertex deletion. In: Thilikos, D.M. (ed.) Graph-Theoretic Concepts in Computer Science, Volume 6410 of Lecture Notes in Computer Science, pp. 232\u2013243. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-16926-7_22"},{"issue":"4","key":"230_CR41","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1007\/s00453-012-9661-3","volume":"65","author":"P van\u2019t Hof","year":"2013","unstructured":"van\u2019t Hof, P., Villanger, Y.: Proper interval vertex deletion. Algorithmica 65(4), 845\u2013867 (2013)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0230-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0230-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0230-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,14]],"date-time":"2019-09-14T18:17:44Z","timestamp":1568485064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0230-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,21]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["230"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0230-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,10,21]]}}}