{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T16:24:48Z","timestamp":1789921488449,"version":"4.0.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319123394","type":"print"},{"value":"9783319123400","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12340-0_29","type":"book-chapter","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T04:27:23Z","timestamp":1413779243000},"page":"348-359","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Parameterized Edge Hamiltonicity"],"prefix":"10.1007","author":[{"given":"Michael","family":"Lampis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yushi","family":"Uno","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"issue":"4","key":"29_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(81)90048-X","volume":"13","author":"AA Bertossi","year":"1981","unstructured":"Bertossi, A.A.: The edge Hamiltonian path problem is NP-complete. Inf. Process. Lett. 13(4), 157\u2013159 (1981)","journal-title":"Inf. Process. Lett."},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An $$O(c^k n)$$ 5-Approximation algorithm for treewidth. In: FOCS, pp. 499\u2013508. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.60"},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"3","key":"29_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/jgt.3190050312","volume":"5","author":"RA Brualdi","year":"1981","unstructured":"Brualdi, R.A., Shanny, R.F.: Hamiltonian line graphs. J. Graph Theory 5(3), 307\u2013314 (1981)","journal-title":"J. Graph Theory"},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/jgt.3190160209","volume":"16","author":"PA Catlin","year":"1992","unstructured":"Catlin, P.A.: Supereulerian graphs: a survey. J. Graph Theory 16(2), 177\u2013196 (1992)","journal-title":"J. Graph Theory"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1090\/S0002-9947-1968-0231740-1","volume":"134","author":"G Chartrand","year":"1968","unstructured":"Chartrand, G.: On Hamiltonian line-graphs. Trans. Am. Math. Soc. 134, 559\u2013566 (1968)","journal-title":"Trans. Am. Math. Soc."},{"issue":"4","key":"29_CR7","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1002\/jgt.10094","volume":"42","author":"Z-H Chen","year":"2003","unstructured":"Chen, Z.-H., Lai, H.-J., Li, X., Li, D., Mao, J.: Eulerian subgraphs in 3-edge-connected graphs and Hamiltonian line graphs. J. Graph Theory 42(4), 308\u2013319 (2003)","journal-title":"J. Graph Theory"},{"issue":"2","key":"29_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1002\/jgt.3190080210","volume":"8","author":"L Clark","year":"1984","unstructured":"Clark, L.: On Hamiltonian line graphs. J. Graph Theory 8(2), 303\u2013307 (1984)","journal-title":"J. Graph Theory"},{"key":"29_CR9","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction to Algorithms, vol. 2. MIT press Cambridge, Cambridge (2001)"},{"issue":"4","key":"29_CR10","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"29_CR11","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":"29_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Cambridge University Press, New York (2012)"},{"issue":"2","key":"29_CR13","doi-asserted-by":"publisher","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."},{"key":"29_CR14","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2013.11.023","volume":"521","author":"ED Demaine","year":"2014","unstructured":"Demaine, E.D., Demaine, M.L., Harvey, N.J.A., Uehara, R., Uno, T., Uno, Y.: UNO is hard, even for a single player. Theor. Comput. Sci. 521, 51\u201361 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-319-07890-8_13","volume-title":"Fun with Algorithms","author":"P Dey","year":"2014","unstructured":"Dey, P., Goyal, P., Misra, N.: UNO gets easier for a single player. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) FUN 2014. LNCS, vol. 8496, pp. 147\u2013157. Springer, Heidelberg (2014)"},{"key":"29_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"29_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/3-540-45477-2_12","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"W Espelage","year":"2001","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 117\u2013128. Springer, Heidelberg (2001)"},{"key":"29_CR18","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, vol. 3. Springer, Berlin (2006)"},{"key":"29_CR19","first-page":"825","volume-title":"SODA","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Clique-width: on the price of generality. In: Mathieu, C. (ed.) SODA, pp. 825\u2013834. SIAM, Philadelphia (2009)"},{"key":"29_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-40064-8_19","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F Gurski","year":"2000","unstructured":"Gurski, F., Wanke, E.: The tree-width of clique-width bounded graphs without $$K_{n,n}$$. In: Brandes, U., Wagner, D. (eds.) WG 2000. LNCS, vol. 1928, pp. 196\u2013205. Springer, Heidelberg (2000)"},{"issue":"22","key":"29_CR21","doi-asserted-by":"publisher","first-page":"2734","DOI":"10.1016\/j.disc.2007.01.020","volume":"307","author":"F Gurski","year":"2007","unstructured":"Gurski, F., Wanke, E.: Line graphs of bounded clique-width. Discrete Math. 307(22), 2734\u20132754 (2007)","journal-title":"Discrete Math."},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"701","DOI":"10.4153\/CMB-1965-051-3","volume":"8","author":"F Harary","year":"1965","unstructured":"Harary, F., Nash-Williams, C.S.J.: On Eulerian and Hamiltonian graphs and line graphs. Can. Math. Bull. 8, 701\u2013709 (1965)","journal-title":"Can. Math. Bull."},{"issue":"3","key":"29_CR23","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlin\u011bn\u1ef3","year":"2008","unstructured":"Hlin\u011bn\u1ef3, P., Oum, S.-I., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"issue":"1","key":"29_CR24","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0012-365X(97)81820-1","volume":"178","author":"H-J Lai","year":"1998","unstructured":"Lai, H.-J.: Eulerian subgraphs containing given vertices and hamiltonian line graphs. Discrete Math. 178(1), 93\u2013107 (1998)","journal-title":"Discrete Math."},{"issue":"1","key":"29_CR25","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(93)90191-B","volume":"46","author":"T-H Lai","year":"1993","unstructured":"Lai, T.-H., Wei, S.-S.: The edge Hamiltonian path problem is NP-complete for bipartite graphs. Inf. Process. Lett. 46(1), 21\u201326 (1993)","journal-title":"Inf. Process. Lett."},{"key":"29_CR26","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms: Oxford Lecture Series in Mathematics and Its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms: Oxford Lecture Series in Mathematics and Its Applications. OUP, Oxford (2006)"},{"issue":"4","key":"29_CR27","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S-I Oum","year":"2006","unstructured":"Oum, S.-I., 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":"29_CR28","series-title":"Lecture Notes In Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-3-642-39071-5_25","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2013","author":"I Razgon","year":"2013","unstructured":"Razgon, I., Petke, J.: Cliquewidth and knowledge compilation. In: J\u00e4rvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 335\u2013350. Springer, Heidelberg (2013)"},{"issue":"4","key":"29_CR29","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.dam.2010.08.027","volume":"159","author":"Z Ryj\u00e1cek","year":"2011","unstructured":"Ryj\u00e1cek, Z., Woeginger, G.J., Xiong, L.: Hamiltonian index is NP-complete. Discrete Appl. Math. 159(4), 246\u2013250 (2011)","journal-title":"Discrete Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12340-0_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T14:25:40Z","timestamp":1675347940000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12340-0_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319123394","9783319123400"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12340-0_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"21 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}