{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T03:28:21Z","timestamp":1784086101507,"version":"3.55.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,19]],"date-time":"2019-12-19T00:00:00Z","timestamp":1576713600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,19]],"date-time":"2019-12-19T00:00:00Z","timestamp":1576713600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"crossref","award":["ANR-15-CE40-0009"],"award-info":[{"award-number":["ANR-15-CE40-0009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-15-CE40-0009"],"award-info":[{"award-number":["ANR-15-CE40-0009"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["648527"],"award-info":[{"award-number":["648527"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation Korea","doi-asserted-by":"crossref","award":["NRF-2018R1D1A1B07050294"],"award-info":[{"award-number":["NRF-2018R1D1A1B07050294"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00663-9","type":"journal-article","created":{"date-parts":[[2019,12,19]],"date-time":"2019-12-19T15:02:58Z","timestamp":1576767778000},"page":"1654-1674","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6270-3663","authenticated-orcid":false,"given":"Benjamin","family":"Bergougnoux","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1820-1962","authenticated-orcid":false,"given":"O-joung","family":"Kwon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,12,19]]},"reference":[{"issue":"2","key":"663_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"663_CR2","doi-asserted-by":"publisher","unstructured":"Bergougnoux, B., Kant\u00e9, M.M.: More applications of the d-neighbor equivalence: connectivity and acyclicity constraints. In: 27th Annual European Symposium on Algorithms, ESA 2019, pp. 17:1\u201317:14. Munich\/Garching, Germany, September 9\u201311, 2019. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.17","DOI":"10.4230\/LIPIcs.ESA.2019.17"},{"key":"663_CR3","unstructured":"Bergougnoux, B., Kant\u00e9, M.M., Kwon, O.: An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width. In: Algorithms and Data Structures\u201415th International Symposium, WADS 2017, St. John\u2019s, NL, Canada, July 31\u2013August 2, 2017, Proceedings, pp. 121\u2013132 (2017)"},{"issue":"1\u20132","key":"663_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H Bodlaender","year":"1998","unstructured":"Bodlaender, H.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"663_CR5","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inform. Comput. 243, 86\u2013111 (2015)","journal-title":"Inform. Comput."},{"issue":"5&6","key":"663_CR6","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5&6), 555\u2013581 (1992)","journal-title":"Algorithmica"},{"key":"663_CR7","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2013.01.009","volume":"511","author":"B-M Bui-Xuan","year":"2013","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theor. Comput. Sci. 511, 66\u201376 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"663_CR8","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0168-0072(90)90027-Y","volume":"49","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs IV: definability properties of equational graphs. Ann. Pure Appl. Log. 49(3), 193\u2013255 (1990)","journal-title":"Ann. Pure Appl. Log."},{"key":"663_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic. Volume 138 of Encyclopedia of Mathematics and its Applications","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. Volume 138 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2012). A language-theoretic approach, with a foreword by Maurice Nivat"},{"issue":"2","key":"663_CR10","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"663_CR11","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."},{"issue":"1\u20132","key":"663_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci. 109(1\u20132), 49\u201382 (1993)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"663_CR13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"key":"663_CR14","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 (extended abstract). In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2011, pp. 150\u2013159. IEEE Computer Society, Los Alamitos, CA (2011)","DOI":"10.1109\/FOCS.2011.23"},{"key":"663_CR15","volume-title":"Graph Theory. Number 173 in Graduate Texts in Mathematics","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Number 173 in Graduate Texts in Mathematics, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"key":"663_CR16","doi-asserted-by":"crossref","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: Graph-theoretic concepts in computer science (Boltenhagen, 2001). Volume 2204 of Lecture Notes in Computer Science, pp. 117\u2013128. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45477-2_12"},{"issue":"2","key":"663_CR17","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math. 23(2), 909\u2013939 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"663_CR18","volume-title":"Eulerian Graphs and Related Topics","author":"H Fleischner","year":"1990","unstructured":"Fleischner, H.: Eulerian Graphs and Related Topics, vol. 1. Elsevier, Amsterdam (1990)"},{"issue":"5","key":"663_CR19","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"663_CR20","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541\u20131563 (2014)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"663_CR21","first-page":"9:1","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algorithms 15(1), 9:1\u20139:27 (2019)","journal-title":"ACM Trans. Algorithms"},{"key":"663_CR22","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Obdr\u017e\u00e1lek, J.: Clique-width: when hard does not mean impossible. In: 28th International Symposium on Theoretical Aspects of Computer Science. Volume 9 of LIPIcs Leibniz International Proceedings in Informatics, pp. 404\u2013415. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2011)"},{"key":"663_CR23","unstructured":"Gurski, F.: A comparison of two approaches for polynomial time algorithms computing basic graph parameters. CoRR (2008). arXiv:0806.4073"},{"issue":"3","key":"663_CR24","doi-asserted-by":"publisher","first-page":"1012","DOI":"10.1137\/070685920","volume":"38","author":"P Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM J. Comput. 38(3), 1012\u20131032 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"663_CR25","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Appl. Math. 126(2\u20133), 197\u2013221 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"663_CR26","first-page":"76","volume":"18","author":"A Kotzig","year":"1968","unstructured":"Kotzig, A.: Moves without forbidden transitions in a graph. Matematick\u1ef3 \u010dasopis 18(1), 76\u201380 (1968)","journal-title":"Matematick\u1ef3 \u010dasopis"},{"issue":"4","key":"663_CR27","doi-asserted-by":"publisher","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. Combin. Theory Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Combin. Theory Ser. B"},{"key":"663_CR28","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7\u20139, 2009. Proceedings, pp. 566\u2013577 (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00663-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00663-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00663-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,18]],"date-time":"2020-12-18T01:06:28Z","timestamp":1608253588000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00663-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,19]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["663"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00663-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,19]]},"assertion":[{"value":"28 September 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}