{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T11:55:26Z","timestamp":1782906926733,"version":"3.54.5"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1007\/s00453-011-9578-2","type":"journal-article","created":{"date-parts":[[2011,9,28]],"date-time":"2011-09-28T11:05:08Z","timestamp":1317207908000},"page":"170-188","source":"Crossref","is-referenced-by-count":13,"title":["An Improved FPT Algorithm and a Quadratic Kernel for Pathwidth One Vertex Deletion"],"prefix":"10.1007","volume":"64","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2011,9,29]]},"reference":[{"key":"9578_CR1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.endm.2004.03.008","volume":"17","author":"C. \u00c0lvarez","year":"2004","unstructured":"\u00c0lvarez, C., Serna, M.J.: The proper interval colored graph problem for caterpillar trees (extended abstract). Electron. Notes Discrete Math. 17, 23\u201328 (2004)","journal-title":"Electron. Notes Discrete Math."},{"key":"9578_CR2","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"CSL","author":"S. Arnborg","year":"1990","unstructured":"Arnborg, S., Proskurowski, A., Seese, D.: Monadic second order logic, tree automata and forbidden minors. In: B\u00f6rger, E., B\u00fcning, H.K., Richter, M.M., Sch\u00f6nfeld, W. (eds.) CSL. Lecture Notes in Computer Science, vol.\u00a0533, pp.\u00a01\u201316. Springer, Berlin (1990)"},{"issue":"4","key":"9578_CR3","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"S.F. Assmann","year":"1981","unstructured":"Assmann, S.F., Peck, G.W., Syslo, M.M., Zak, J.: The bandwidth of caterpillars with hairs of length\u00a01 and\u00a02. SIAM J. Algebr. Discrete Methods 2(4), 387\u2013393 (1981)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"9578_CR4","series-title":"Lecture Notes in Computer Science","first-page":"93","volume-title":"SWAT","author":"Y. Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT. Lecture Notes in Computer Science, vol.\u00a06139, pp.\u00a093\u2013104. Springer, Berlin (2010)"},{"key":"9578_CR5","doi-asserted-by":"crossref","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Wojtaszczyk, J.O.: Solving connectivity problems parameterized by treewidth in single exponential time. In: FOCS (to appear), see also CoRR. arXiv:1103.0534 [cs.Ds] (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"9578_CR6","first-page":"251","volume-title":"STOC","author":"H. Dell","year":"2010","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Schulman, L.J. (ed.) STOC, pp.\u00a0251\u2013260. ACM, New York (2010)"},{"key":"9578_CR7","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2006","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics. Springer, Berlin (2006)"},{"key":"9578_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"2","key":"9578_CR9","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00453-005-1181-y","volume":"45","author":"V. Dujmovic","year":"2006","unstructured":"Dujmovic, V., Fellows, M.R., Hallett, M.T., Kitching, M., Liotta, G., McCartin, C., Nishimura, N., Ragde, P., Rosamond, F.A., Suderman, M., Whitesides, S., Wood, D.R.: A\u00a0fixed-parameter approach to 2-layer planarization. Algorithmica 45(2), 159\u2013182 (2006)","journal-title":"Algorithmica"},{"key":"9578_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-540-30577-4_17","volume-title":"SOFSEM","author":"H. Fernau","year":"2005","unstructured":"Fernau, H.: Two-layer planarization: improving on parameterized algorithmics. In: Vojt\u00e1s, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM. Lecture Notes in Computer Science, vol.\u00a03381, pp.\u00a0137\u2013146. Springer, Berlin (2005)"},{"key":"9578_CR11","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, 1st edn. Texts in Theoretical Computer Science. An EATCS Series. Springer, Secaucus (2006)","edition":"1"},{"issue":"3","key":"9578_CR12","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1016\/j.tcs.2006.07.015","volume":"363","author":"M. Lin","year":"2006","unstructured":"Lin, M., Lin, Z., Xu, J.: Graph bandwidth of weighted caterpillars. Theor. Comput. Sci. 363(3), 266\u2013277 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9578_CR13","series-title":"Annals of Discrete Mathematics","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. Annals of Discrete Mathematics. North-Holland, Amsterdam (1986)"},{"key":"9578_CR14","first-page":"248","volume-title":"FOCS","author":"M. Mucha","year":"2004","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: FOCS, pp. 248\u2013255. IEEE Comp. Soc., Los Alamitos (2004)"},{"key":"9578_CR15","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, London (2006)"},{"issue":"4","key":"9578_CR16","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1215\/S0012-7094-55-02268-7","volume":"22","author":"O. Ore","year":"1955","unstructured":"Ore, O.: Graphs and matching theorems. Duke Math. J. 22(4), 625\u2013639 (1955)","journal-title":"Duke Math. J."},{"issue":"3","key":"9578_CR17","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C.H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H.: The NP-completeness of the bandwidth minimization problem. Computing 16(3), 263\u2013270 (1976)","journal-title":"Computing"},{"key":"9578_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/978-3-642-16926-7_19","volume-title":"WG","author":"G. Philip","year":"2010","unstructured":"Philip, G., Raman, V., Villanger, Y.: A quartic kernel for pathwidth-one vertex deletion. In: Thilikos, D.M. (ed.) WG. Lecture Notes in Computer Science, vol.\u00a06410, pp.\u00a0196\u2013207 (2010)"},{"issue":"1","key":"9578_CR19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J.\u00a0Comb. Theory, Ser. B 35(1), 39\u201361 (1983)","journal-title":"J.\u00a0Comb. Theory, Ser. B"},{"issue":"3","key":"9578_CR20","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J.\u00a0Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J.\u00a0Algorithms"},{"key":"9578_CR21","unstructured":"Suderman, M.: Layered graph drawing. Ph.D. thesis, School of Computer Science, McGill University Montre\u00e1l (2005)"},{"issue":"2","key":"9578_CR22","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S. Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A 4k 2 kernel for feedback vertex set. ACM Transactions on Algorithms 6(2), 32:1\u201332:8 (2010)","journal-title":"ACM Transactions on Algorithms"},{"key":"9578_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/978-3-642-13562-0_39","volume-title":"TAMC","author":"J. Uhlmann","year":"2010","unstructured":"Uhlmann, J., Weller, M.: Two-layer planarization parameterized by feedback edge set. In: Kratochv\u00edl,\u00a0J., Li,\u00a0A., Fiala, J., Kolman, P. (eds.) TAMC. Lecture Notes in Computer Science, vol.\u00a06108, pp.\u00a0431\u2013442. Springer, Berlin (2010)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/s00453-011-9578-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,16]],"date-time":"2019-06-16T13:28:28Z","timestamp":1560691708000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9578-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,29]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,9]]}},"alternative-id":["9578"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9578-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,29]]}}}