{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T01:17:52Z","timestamp":1770513472930,"version":"3.49.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,4,1]],"date-time":"2012-04-01T00:00:00Z","timestamp":1333238400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Suomen Akatemia","doi-asserted-by":"publisher","award":["117499 (P.K.) and 109101 (M.K.)"],"award-info":[{"award-number":["117499 (P.K.) and 109101 (M.K.)"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>\n            We show that the traveling salesman problem in bounded-degree graphs can be solved in time\n            <jats:italic>O<\/jats:italic>\n            ((2-\u03f5)\n            <jats:italic>\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            ), where \u03f5 &gt; 0 depends only on the degree bound but not on the number of cities,\n            <jats:italic>n<\/jats:italic>\n            . The algorithm is a variant of the classical dynamic programming solution due to Bellman, and, independently, Held and Karp. In the case of bounded integer weights on the edges, we also give a polynomial-space algorithm with running time\n            <jats:italic>O<\/jats:italic>\n            ((2-\u03f5)\n            <jats:italic>\n              <jats:sup>n<\/jats:sup>\n            <\/jats:italic>\n            ) on bounded-degree graphs. In addition, we present an analogous analysis of Ryser's algorithm for the permanent of matrices with a bounded number of nonzero entries in each column.\n          <\/jats:p>","DOI":"10.1145\/2151171.2151181","type":"journal-article","created":{"date-parts":[[2012,4,24]],"date-time":"2012-04-24T18:41:10Z","timestamp":1335292870000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["The traveling salesman problem in bounded degree graphs"],"prefix":"10.1145","volume":"8","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Lund University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[{"name":"IT University of Copenhagen, Denmark and Lund University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology and University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikko","family":"Koivisto","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology and University of Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,4,25]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Applegate D. L. Bixby R. E. Chvatal V. and Cook W. J. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press Princeton NJ.   Applegate D. L. Bixby R. E. Chvatal V. and Cook W. J. 2006. The Traveling Salesman Problem: A Computational Study. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0072-0"},{"key":"e_1_2_1_3_1","volume-title":"Combinatorial Analysis","author":"Bellman R.","unstructured":"Bellman , R. 1960. Combinatorial processes and dynamic programming . In Combinatorial Analysis , R. Bellman and M. Hall, Jr. Eds., American Mathematical Society , Providence, RI , 217--249. Bellman, R. 1960. Combinatorial processes and dynamic programming. In Combinatorial Analysis, R. Bellman and M. Hall, Jr. Eds., American Mathematical Society, Providence, RI, 217--249."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_17"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STAC), S. Albers and P. Weil Eds., 85--96","author":"Bj\u00f6rklund A.","unstructured":"Bj\u00f6rklund , A. , Husfeldt , T. , Kaski , P. , and Koivisto , M . 2008b. Trimmed Moebius inversion and graphs of bounded degree . In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STAC), S. Albers and P. Weil Eds., 85--96 . Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., and Koivisto, M. 2008b. Trimmed Moebius inversion and graphs of bounded degree. In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STAC), S. Albers and P. Weil Eds., 85--96."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90019-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00137"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972986.8"},{"key":"e_1_2_1_10_1","unstructured":"Gutin G. and Punnen A. P. 2002. The Traveling Salesman Problem and its Variations. Kluwer Amsterdam.  Gutin G. and Punnen A. P. 2002. The Traveling Salesman Problem and its Variations. Kluwer Amsterdam."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Iwama K.\n     and \n      Nakashima T\n  . \n  2007\n  . An improved exact algorithm for cubic graph TSP. In Proceedings of the Computing and Combinatorics 13th Annual International Conference (COCOON). G. Lin Ed. Lecture Notes in Computer Science vol. \n  459 Springer Berlin 108--117.   Iwama K. and Nakashima T. 2007. An improved exact algorithm for cubic graph TSP. In Proceedings of the Computing and Combinatorics 13th Annual International Conference (COCOON). G. Lin Ed. Lecture Notes in Computer Science vol. 459 Springer Berlin 108--117.","DOI":"10.1007\/978-3-540-73545-8_13"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90044-X"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/800179.810218"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Lawler E. L. Lenstra J. K. Kan A. H. G. R. and Shmoys D. B. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.  Lawler E. L. Lenstra J. K. Kan A. H. G. R. and Shmoys D. B. 1985. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley.","DOI":"10.2307\/2582681"},{"key":"e_1_2_1_16_1","unstructured":"Radhakrishnan J. 2001. Entropy and counting. In Computational Mathematics Modelling and Algorithms J. C. Mishra Ed. Narosa Publishers.  Radhakrishnan J. 2001. Entropy and counting. In Computational Mathematics Modelling and Algorithms J. C. Mishra Ed. Narosa Publishers."},{"key":"e_1_2_1_17_1","volume-title":"Combinatorial Mathematics","author":"Ryser H. J.","unstructured":"Ryser , H. J. 1963. Combinatorial Mathematics . The Mathematical Association of America , Washington, D.C. Ryser, H. J. 1963. Combinatorial Mathematics. The Mathematical Association of America, Washington, D.C."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.06.007"},{"key":"e_1_2_1_19_1","volume-title":"Introduction to Graph Theory","author":"West D. E.","unstructured":"West , D. E. 2001. Introduction to Graph Theory 2 nd Ed. Prentice--Hall , Englewood Cliffs, NJ . West, D. E. 2001. Introduction to Graph Theory 2nd Ed. Prentice--Hall, Englewood Cliffs, NJ.","edition":"2"},{"key":"e_1_2_1_20_1","volume-title":"Combinatorial Optimization---Eureka, You Shrink! Lecture Notes in Computer Science","author":"Woeginger G. J.","unstructured":"Woeginger , G. J. 2003. Exact algorithms for NP-hard problems: A survey . In Combinatorial Optimization---Eureka, You Shrink! Lecture Notes in Computer Science , vol. 2570 , Springer , Berlin , 185--207. Woeginger, G. J. 2003. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization---Eureka, You Shrink! Lecture Notes in Computer Science, vol. 2570, Springer, Berlin, 185--207."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151181","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2151171.2151181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:19Z","timestamp":1750241179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2151171.2151181"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.1145\/2151171.2151181"],"URL":"https:\/\/doi.org\/10.1145\/2151171.2151181","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}