{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:01:28Z","timestamp":1743048088158,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642280498"},{"type":"electronic","value":"9783642280504"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":[[2012]]},"DOI":"10.1007\/978-3-642-28050-4_20","type":"book-chapter","created":{"date-parts":[[2012,3,8]],"date-time":"2012-03-08T23:40:26Z","timestamp":1331250026000},"page":"246-258","source":"Crossref","is-referenced-by-count":6,"title":["On Cutwidth Parameterized by Vertex Cover"],"prefix":"10.1007","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","reference":[{"key":"20_CR1","doi-asserted-by":"publisher","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.\u00a025, 403\u2013423 (1973)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"20_CR2","doi-asserted-by":"publisher","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\u00a09(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: FOCS, pp. 173\u2013182 (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"20_CR4","doi-asserted-by":"publisher","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. Journal of Discrete Algorithms\u00a06, 618\u2013626 (2008)","journal-title":"Journal of Discrete Algorithms"},{"key":"20_CR5","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.\u00a09, pp. 165\u2013176. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2011)"},{"key":"20_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-642-22006-7_37","volume-title":"Automata, Languages and Programming","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 2011. LNCS, vol.\u00a06755, pp. 437\u2013448. Springer, Heidelberg (2011)"},{"key":"20_CR7","unstructured":"Bodlaender, H.L., Thomasse, S., Yeo, A.: Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels, technical Report UU-CS-2008-030, Institute of Information and Computing Sciences, Utrecht University, Netherlands (2008)"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Botafogo, R.A.: Cluster analysis for hypertext systems. In: SIGIR, pp. 116\u2013125 (1993)","DOI":"10.1145\/160688.160704"},{"key":"20_CR9","doi-asserted-by":"publisher","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 Journal on Computing\u00a014, 158\u2013177 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR10","doi-asserted-by":"publisher","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. Journal of Algorithms\u00a039, 78\u2013117 (2001)","journal-title":"Journal of Algorithms"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-92182-0_28","volume-title":"Algorithms and Computation","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 2008. LNCS, vol.\u00a05369, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"issue":"3","key":"20_CR12","doi-asserted-by":"publisher","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.\u00a038(3), 1058\u20131079 (2008)","journal-title":"SIAM J. Comput."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC 2008: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 133\u2013142. ACM (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"20_CR14","unstructured":"Gavril, F.: Some np-complete problems on graphs, pp. 91\u201395 (1977)"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-16926-7_9","volume-title":"Graph Theoretic Concepts in Computer Science","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 2010. LNCS, vol.\u00a06410, pp. 75\u201387. Springer, Heidelberg (2010)"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-540-92248-3_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Heggernes","year":"2008","unstructured":"Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 218\u2013229. Springer, Heidelberg (2008)"},{"issue":"1","key":"20_CR17","doi-asserted-by":"publisher","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. Journal of the Society for Industrial and Applied Mathematics\u00a010(1), 196\u2013210 (1962)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Jansen, B.M.P., Kratsch, S.: Data reduction for graph coloring problems. CoRR abs\/1104.4229 (2011)","DOI":"10.1007\/978-3-642-22953-4_8"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Junguer, M., Reinelt, G., Rinaldi, G.: The travelling salesman problem. In: Handbook on Operations Research and Management Sciences, pp. 225\u2013330 (1995)","DOI":"10.1016\/S0927-0507(05)80121-5"},{"issue":"2","key":"20_CR20","doi-asserted-by":"publisher","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.\u00a029(2), 492\u2013514 (1999)","journal-title":"SIAM J. Comput."},{"key":"20_CR21","doi-asserted-by":"publisher","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.\u00a01, 49\u201351 (1982)","journal-title":"Oper. Res. Lett."},{"key":"20_CR22","doi-asserted-by":"publisher","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. Journal of the ACM\u00a046, 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"key":"20_CR23","doi-asserted-by":"publisher","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 Applied Mathematics\u00a023, 243\u2013265 (1989)","journal-title":"Discrete Applied Mathematics"},{"key":"20_CR24","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a058, 209\u2013229 (1988)","journal-title":"Theoretical Computer Science"},{"key":"20_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/3-540-60313-1_166","volume-title":"Algorithms - ESA \u201995","author":"P. Mutzel","year":"1995","unstructured":"Mutzel, P.: A Polyhedral Approach to Planar Augmentation and Related Problems. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol.\u00a0979, pp. 494\u2013507. Springer, Heidelberg (1995)"},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-11269-0_27","volume-title":"Parameterized and Exact Computation","author":"K. Suchan","year":"2009","unstructured":"Suchan, K., Villanger, Y.: Computing Pathwidth Faster than 2. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 324\u2013335. Springer, Heidelberg (2009)"},{"key":"20_CR27","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. Journal of Algorithms\u00a056, 24\u201349 (2005)","journal-title":"Journal of Algorithms"},{"key":"20_CR28","doi-asserted-by":"publisher","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. Journal of the ACM\u00a032, 950\u2013988 (1985)","journal-title":"Journal of the ACM"},{"key":"20_CR29","doi-asserted-by":"publisher","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. Chinese Univ. Ser.\u00a0B (English edition)\u00a010, 337\u2013344 (1995)","journal-title":"Appl. Math. J. Chinese Univ. Ser.\u00a0B (English edition)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-28050-4_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T09:49:26Z","timestamp":1556444966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-28050-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642280498","9783642280504"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-28050-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}