{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:14:43Z","timestamp":1759637683889},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,9,26]],"date-time":"2011-09-26T00:00:00Z","timestamp":1316995200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s00453-011-9576-4","type":"journal-article","created":{"date-parts":[[2011,9,25]],"date-time":"2011-09-25T16:43:27Z","timestamp":1316969007000},"page":"129-145","source":"Crossref","is-referenced-by-count":3,"title":["Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"Hajo","family":"Broersma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,9,26]]},"reference":[{"issue":"4","key":"9576_CR1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0020-0190(93)90033-6","volume":"47","author":"E.T. Bax","year":"1993","unstructured":"Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian path problem. Inf. Process. Lett. 47(4), 203\u2013207 (1993)","journal-title":"Inf. Process. Lett."},{"key":"9576_CR2","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1109\/FOCS.2010.24","volume-title":"51st Annual Symposium on Foundations of Computer Science (FOCS 2010)","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp. 173\u2013182. IEEE Computer Society, Los Alamitos (2010)"},{"key":"9576_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/978-3-540-70575-8_17","volume-title":"35th International Colloquium on Automata, Languages and Programming (ICALP 2008)","author":"A. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund,\u00a0A., Husfeldt, T., Kaski, P., Koivisto, M.: The travelling salesman problem in bounded degree graphs. In: Aceto, L., Damgaard, I., Goldberg, L.A., Halldorsson, M.M., Ingolfsdottir, A., Walukiewicz,\u00a0I. (eds.) 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). Lecture Notes in Computer Science, vol.\u00a05125, pp. 198\u2013209. Springer, Berlin (2008)"},{"key":"9576_CR4","series-title":"Lecture Notes in Computer Science","first-page":"44","volume-title":"35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009)","author":"H.J. Broersma","year":"2009","unstructured":"Broersma, H.J., Fomin, F.V., van \u2019t Hof, P., Paulusma, D.: Fast exact algorithms for hamiltonicity in claw-free graphs. In: Paul, C., Habib, M. (eds.) 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009) Lecture Notes in Computer Science, vol.\u00a05911, pp. 44\u201353. Springer, Berlin (2009)"},{"issue":"3","key":"9576_CR5","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.jda.2009.07.001","volume":"8","author":"H.J. Broersma","year":"2010","unstructured":"Broersma, H.J., Paulusma, D.: Computing sharp 2-factors in claw-free graphs. J. Discrete Algorithms 8(3), 321\u2013329 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"9576_CR6","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"9576_CR7","first-page":"631","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008)","author":"F. Dorn","year":"2008","unstructured":"Dorn, F., Fomin, F.V., Thilikos, D.M.: Catalan structures and dynamic programming on H-minor-free graphs. In: Teng, S.-H. (ed.) Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 631\u2013640. ACM-SIAM, Philadelphia (2008)"},{"issue":"3","key":"9576_CR8","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F. Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut branch decompositions. Algorithmica 58(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"issue":"1","key":"9576_CR9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.7155\/jgaa.00137","volume":"11","author":"D. Eppstein","year":"2007","unstructured":"Eppstein, D.: The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl. 11(1), 61\u201381 (2007)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1\u20133","key":"9576_CR10","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0012-365X(96)00045-3","volume":"164","author":"R. Faudree","year":"1997","unstructured":"Faudree, R., Flandrin, E., Ryj\u00e1\u010dek, Z.: Claw-free graphs\u2014a survey. Discrete Math. 164(1\u20133), 87\u2013147 (1997)","journal-title":"Discrete Math."},{"key":"9576_CR11","volume-title":"Computers Intractability","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers Intractability. Freeman, New York (1979)"},{"issue":"35","key":"9576_CR12","doi-asserted-by":"crossref","first-page":"4579","DOI":"10.1016\/j.tcs.2011.04.038","volume":"412","author":"H. Gebauer","year":"2011","unstructured":"Gebauer, H.: Finding and enumerating Hamilton cycles in 4-regular graphs. Theor. Comput. Sci. 412(35), 4579\u20134591 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9576_CR13","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)"},{"issue":"6","key":"9576_CR14","doi-asserted-by":"crossref","first-page":"701","DOI":"10.4153\/CMB-1965-051-3","volume":"8","author":"F. Harary","year":"1965","unstructured":"Harary, F., Nash-Williams, C.St.J.A.: On Eulerian and Hamiltonian graphs and line graphs. Can. Math. Bull. 8(6), 701\u2013709 (1965)","journal-title":"Can. Math. Bull."},{"issue":"1","key":"9576_CR15","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":"9576_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-3-540-73545-8_13","volume-title":"13th Annual International Computing and Combinatorics Conference (COCOON 2007)","author":"K. Iwama","year":"2007","unstructured":"Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) 13th Annual International Computing and Combinatorics Conference (COCOON 2007). Lecture Notes in Computer Science, vol.\u00a04598, pp. 108\u2013117. Springer, Berlin (2007)"},{"issue":"2","key":"9576_CR17","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(2), 49\u201351 (1982)","journal-title":"Oper. Res. Lett."},{"key":"9576_CR18","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/800179.810218","volume-title":"Proceedings of the ACM Annual Conference (ACM 1977)","author":"S. Kohn","year":"1977","unstructured":"Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the traveling salesman problem. In: Proceedings of the ACM Annual Conference (ACM 1977), pp. 294\u2013300. ACM Press, New York (1977)"},{"key":"9576_CR19","unstructured":"Kuipers, E.J., Veldman, H.J.: Recognizing claw-free Hamiltonian graphs with large minimum degree. Memorandum 1437, University of Twente, Enschede (1998)"},{"issue":"3","key":"9576_CR20","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0166-218X(99)00163-8","volume":"98","author":"M. Li","year":"2000","unstructured":"Li, M., Corneil, D.G., Mendelsohn, E.: Pancyclicity and NP-completeness in planar graphs. Discrete Appl. Math. 98(3), 219\u2013225 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9576_CR21","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(95)00107-3","volume":"70","author":"Z. Lonc","year":"1996","unstructured":"Lonc, Z.: On the complexity of some edge-partition problems for graphs. Discrete Appl. Math. 70(2), 177\u2013183 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"9576_CR22","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H. M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156(1\u20133), 291\u2013298 (1996)","journal-title":"Discrete Math."},{"issue":"4","key":"9576_CR23","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1002\/jgt.3190030405","volume":"3","author":"D.J. Oberly","year":"1979","unstructured":"Oberly, D.J., Simi\u0107, S.K., Sumner, D.P.,: Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian. J. Graph Theory 3(4), 351\u2013356 (1979)","journal-title":"J. Graph Theory"},{"issue":"4","key":"9576_CR24","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/0020-0190(73)90029-X","volume":"2","author":"N.D. Roussopoulos","year":"1973","unstructured":"Roussopoulos, N.D.: A max\u2009{m,n} algorithm for determining the graph H from its line graph G. Inf. Process. Lett. 2(4), 108\u2013112 (1973)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9576_CR25","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1006\/jctb.1996.1732","volume":"70","author":"Z. Ryj\u00e1\u010dek","year":"1997","unstructured":"Ryj\u00e1\u010dek, Z.: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70(2), 217\u2013224 (1997)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9576_CR26","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0095-8956(81)80025-1","volume":"31","author":"C. Thomassen","year":"1981","unstructured":"Thomassen, C., Toft, B.: Non-separating induced cycles in graphs. J. Comb. Theory, Ser. B 31(2), 199\u2013224 (1981)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"3","key":"9576_CR27","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/j.dam.2007.03.023","volume":"156","author":"G.J. Woeginger","year":"2008","unstructured":"Woeginger, G.J.: Open problems around exact algorithms. Discrete Appl. Math. 156(3), 397\u2013405 (2008)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9576-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9576-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9576-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,16]],"date-time":"2019-06-16T08:09:33Z","timestamp":1560672573000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9576-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,26]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["9576"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9576-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9,26]]}}}