{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T13:33:36Z","timestamp":1768916016146,"version":"3.49.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,2,5]],"date-time":"2015-02-05T00:00:00Z","timestamp":1423094400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-015-9970-4","type":"journal-article","created":{"date-parts":[[2015,2,4]],"date-time":"2015-02-04T14:14:53Z","timestamp":1423059293000},"page":"713-741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure"],"prefix":"10.1007","volume":"74","author":[{"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,2,5]]},"reference":[{"key":"9970_CR1","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: Proceedings of 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 173\u2013182 (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"9970_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kasaki, P., Koivisto, M.: The travelling salesman problem in bounded degree graphs. In: Aceto, L., et al. (eds.) ICALP 2008, LNCS 5125, pp. 198\u2013209 (2008)","DOI":"10.1007\/978-3-540-70575-8_17"},{"key":"9970_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In: Fomin, F.V., et al. (eds.) ICALP 2013, LNCS 7965, pp. 196\u2013207 (2013)","DOI":"10.1007\/978-3-642-39206-1_17"},{"issue":"3","key":"9970_CR4","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.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"9970_CR5","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1145\/1198513.1198515","volume":"2","author":"D Eppstein","year":"2006","unstructured":"Eppstein, D.: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans. Algorithms 2(4), 492\u2013509 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9970_CR6","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. Gr. Algorithms Appl. 11(1), 61\u201381 (2007)","journal-title":"J. Gr. Algorithms Appl."},{"key":"9970_CR7","doi-asserted-by":"crossref","unstructured":"Fomin, F., Grandoni, F., Grandoni, F., Kratsch, D.: Measure and conquer: domination: a case study. In: Caires, L., et al. (eds.) ICALP 2005, LNCS 3580, pp. 191\u2013203. Springer, Berlin (2005)","DOI":"10.1007\/11523468_16"},{"key":"9970_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)"},{"issue":"35","key":"9970_CR9","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":"9970_CR10","doi-asserted-by":"crossref","unstructured":"Iwama, K., Nakashima, T.: An improved exact algorithm for cubic graph TSP. In: Lin, G. (ed.) COCOON 2007. LNCS 4598, pp. 108\u2013117 (2007)","DOI":"10.1007\/978-3-540-73545-8_13"},{"key":"9970_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jda.2014.02.001","volume":"27","author":"M Li\u015bkiewicz","year":"2014","unstructured":"Li\u015bkiewicz, M., Schuster, M.R.: A new upper bound for the traveling salesman problem in cubic graphs. J. Discrete Algorithms 27, 1\u201320 (2014)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"9970_CR12","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF03167564","volume":"9","author":"H Nagamochi","year":"1992","unstructured":"Nagamochi, H., Ibaraki, T.: A linear time algorithm for computing 3-edge-connected components in multigraphs. J. Jpn. Soc. Ind. Appl. Math. 9(2), 163\u2013180 (1992)","journal-title":"J. Jpn. Soc. Ind. Appl. Math."},{"key":"9970_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721649","volume-title":"Algorithmic Aspects of Graph Connectivities, Encyclopedia of Mathematics and its Applications","author":"H Nagamochi","year":"2008","unstructured":"Nagamochi, H., Ibaraki, T.: Algorithmic Aspects of Graph Connectivities, Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2008)"},{"key":"9970_CR14","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Junger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization. LNCS 2570, pp. 185\u2013207 (2003)","DOI":"10.1007\/3-540-36478-1_17"},{"key":"9970_CR15","doi-asserted-by":"crossref","unstructured":"Xiao, M., Nagamochi, H.: An improved exact algorithm for TSP in degree- $$4$$ 4 graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) COCOON 2012. LNCS 7434, pp. 74\u201385 (2012)","DOI":"10.1007\/978-3-642-32241-9_7"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9970-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-9970-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-9970-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T23:47:23Z","timestamp":1559087243000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-9970-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,5]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9970"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-9970-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,2,5]]}}}