{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:03:06Z","timestamp":1761807786187},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,11,8]],"date-time":"2012-11-08T00:00:00Z","timestamp":1352332800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,4]]},"DOI":"10.1007\/s00453-012-9707-6","type":"journal-article","created":{"date-parts":[[2012,11,7]],"date-time":"2012-11-07T15:08:31Z","timestamp":1352300911000},"page":"940-953","source":"Crossref","is-referenced-by-count":11,"title":["On Cutwidth Parameterized by Vertex Cover"],"prefix":"10.1007","volume":"68","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,11,8]]},"reference":[{"key":"9707_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D. Adolphson","year":"1973","unstructured":"Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math. 25, 403\u2013423 (1973)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"9707_CR2","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R. Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"9707_CR3","first-page":"173","volume-title":"FOCS","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: FOCS, pp. 173\u2013182. IEEE Comput. Soc., Los Alamitos (2010)"},{"key":"9707_CR4","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1016\/j.jda.2008.03.004","volume":"6","author":"G. Blin","year":"2008","unstructured":"Blin, G., Fertin, G., Hermelin, D., Vialette, S.: Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. J. Discrete Algorithms 6, 618\u2013626 (2008)","journal-title":"J. Discrete Algorithms"},{"issue":"8","key":"9707_CR5","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9707_CR6","first-page":"165","volume-title":"STACS, LIPIcs","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Cross-composition: a new technique for kernelization lower bounds. In: Schwentick, T., D\u00fcrr, C. (eds.) STACS, LIPIcs, vol. 9, pp. 165\u2013176 (2011). Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik"},{"key":"9707_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/978-3-642-22006-7_37","volume-title":"ICALP (1)","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Preprocessing for treewidth: a combinatorial analysis through kernelization. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP (1). Lecture Notes in Computer Science, vol. 6755, pp. 437\u2013448. Springer, Berlin (2011)"},{"key":"9707_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1007\/978-3-642-31155-0_31","volume-title":"SWAT","author":"H.L. Bodlaender","year":"2012","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernel bounds for structural parameterizations of pathwidth. In: Fomin, F.V., Kaski, P. (eds.) SWAT. Lecture Notes in Computer Science, vol.\u00a07357, pp.\u00a0352\u2013363. Springer, Berlin (2012)"},{"issue":"35","key":"9707_CR9","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9707_CR10","first-page":"116","volume-title":"SIGIR","author":"R.A. Botafogo","year":"1993","unstructured":"Botafogo, R.A.: Cluster analysis for hypertext systems. In: Korfhage, R., Rasmussen, E.M., Willett, P. (eds.) SIGIR, pp. 116\u2013125. ACM, New York (1993)"},{"issue":"1","key":"9707_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J. Cai","year":"2005","unstructured":"Cai, J., Chakaravarthy, V.T., Hemaspaandra, L.A., Ogihara, M.: Competing provers yield improved Karp-Lipton collapse results. Inf. Comput. 198(1), 1\u201323 (2005)","journal-title":"Inf. Comput."},{"key":"9707_CR12","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1137\/0214013","volume":"14","author":"M. Chung","year":"1985","unstructured":"Chung, M., Makedon, F., Sudborough, I., Turner, J.: Polynomial time algorithms for the min cut problem on degree restricted trees. SIAM J. Comput. 14, 158\u2013177 (1985)","journal-title":"SIAM J. Comput."},{"key":"9707_CR13","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/jagm.2000.1149","volume":"39","author":"J. Diaz","year":"2001","unstructured":"Diaz, J., Penrose, M., Petit, J., Serna, M.: Approximating layout problems on random geometric graphs. J. Algorithms 39, 78\u2013117 (2001)","journal-title":"J. Algorithms"},{"key":"9707_CR14","doi-asserted-by":"crossref","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. In: FOCS. IEEE Comput. Soc., Los Alamitos (2012, to appear)","DOI":"10.1109\/FOCS.2012.71"},{"key":"9707_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"ISAAC","author":"M.R. Fellows","year":"2008","unstructured":"Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S.H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 5369, pp. 294\u2013305. Springer, Berlin (2008)"},{"issue":"3","key":"9707_CR16","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38(3), 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9707_CR17","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77(1), 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9707_CR18","first-page":"91","volume-title":"11th Conference on Information Sciences and Systems","author":"F. Gavril","year":"1977","unstructured":"Gavril, F.: Some NP-complete problems on graphs. In: 11th Conference on Information Sciences and Systems, pp. 91\u201395 (1977)"},{"key":"9707_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-16926-7_9","volume-title":"WG","author":"P. Heggernes","year":"2010","unstructured":"Heggernes, P., van\u2019t Hof, P., Lokshtanov, D., Nederlof, J.: Computing the cutwidth of bipartite permutation graphs in linear time. In: Thilikos, D.M. (ed.) WG. Lecture Notes in Computer Science, vol.\u00a06410, pp.\u00a075\u201387 (2010)"},{"issue":"3","key":"9707_CR20","doi-asserted-by":"crossref","first-page":"1418","DOI":"10.1137\/080741197","volume":"25","author":"P. Heggernes","year":"2011","unstructured":"Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs and threshold graphs. SIAM J. Discrete Math. 25(3), 1418\u20131437 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9707_CR21","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M. Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"9707_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1007\/978-3-642-22953-4_8","volume-title":"FCT","author":"B.M.P. Jansen","year":"2011","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. In: Owe, O., Steffen, M., Telle, J.A. (eds.) FCT. Lecture Notes in Computer Science, vol. 6914, pp. 90\u2013101. Springer, Berlin (2011)"},{"key":"9707_CR23","first-page":"225","volume-title":"Handbook on Operations Research and Management Sciences","author":"M. Junguer","year":"1995","unstructured":"Junguer, M., Reinelt, G., Rinaldi, G.: The travelling salesman problem. In: Handbook on Operations Research and Management Sciences, vol. 7, pp. 225\u2013330 (1995)"},{"issue":"2","key":"9707_CR24","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1137\/S0097539796298340","volume":"29","author":"D.R. Karger","year":"1999","unstructured":"Karger, D.R.: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J. Comput. 29(2), 492\u2013514 (1999)","journal-title":"SIAM J. Comput."},{"key":"9707_CR25","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion and exclusion. Oper. Res. Lett. 1, 49\u201351 (1982)","journal-title":"Oper. Res. Lett."},{"key":"9707_CR26","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F. Leighton","year":"1999","unstructured":"Leighton, F., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46, 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"9707_CR27","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(89)90016-4","volume":"23","author":"F. Makedon","year":"1989","unstructured":"Makedon, F., Sudborough, I.H.: On minimizing width in linear layouts. Discrete Appl. Math. 23, 243\u2013265 (1989)","journal-title":"Discrete Appl. Math."},{"key":"9707_CR28","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.H.: Min cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58, 209\u2013229 (1988)","journal-title":"Theor. Comput. Sci."},{"key":"9707_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1007\/3-540-60313-1_166","volume-title":"ESA","author":"P. Mutzel","year":"1995","unstructured":"Mutzel, P.: A polyhedral approach to planar augmentation and related problems. In: Spirakis, P.G. (ed.) ESA. Lecture Notes in Computer Science, vol. 979, pp. 494\u2013507. Springer, Berlin (1995)"},{"key":"9707_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/978-3-642-11269-0_27","volume-title":"IWPEC","author":"K. Suchan","year":"2009","unstructured":"Suchan, K., Villanger, Y.: Computing pathwidth faster than 2 n . In: Chen, J., Fomin, F.V. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 5917, pp. 324\u2013335. Springer, Berlin (2009)"},{"key":"9707_CR31","first-page":"24","volume":"56","author":"D.M. Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: Algorithms for partial w-trees of bounded degree. J. Algorithms 56, 24\u201349 (2005)","journal-title":"J. Algorithms"},{"key":"9707_CR32","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M. Yannakakis","year":"1985","unstructured":"Yannakakis, M.: A polynomial algorithm for the min cut linear arrangement of trees. J. ACM 32, 950\u2013988 (1985)","journal-title":"J. ACM"},{"key":"9707_CR33","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C.K. Yap","year":"1983","unstructured":"Yap, C.K.: Some consequences of non-uniform conditions on uniform classes. Theor. Comput. Sci. 26, 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"9707_CR34","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF02662875","volume":"10","author":"J. Yuan","year":"1995","unstructured":"Yuan, J., Zhou, S.: Optimal labelling of unit interval graphs. Appl. Math. J. Chin. Univ. Ser. A 10, 337\u2013344 (1995)","journal-title":"Appl. Math. J. Chin. Univ. Ser. A"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9707-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9707-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9707-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T14:15:48Z","timestamp":1551190548000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9707-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,8]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,4]]}},"alternative-id":["9707"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9707-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11,8]]}}}