{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T21:50:01Z","timestamp":1742939401164,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":35,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789811981517"},{"type":"electronic","value":"9789811981524"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[[2022]]},"DOI":"10.1007\/978-981-19-8152-4_5","type":"book-chapter","created":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T16:04:02Z","timestamp":1670601842000},"page":"77-95","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Polynomial Randomized Algorithm to\u00a0Compute Bounded Degree Graph for\u00a0TSP Based on\u00a0Frequency Quadrilaterals"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4029-4018","authenticated-orcid":false,"given":"Yong","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,10]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841103","volume-title":"In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation","author":"WJ Cook","year":"2011","unstructured":"Cook, W.J.: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton (2011)"},{"key":"5_CR2","series-title":"Combinatorial Optimization","doi-asserted-by":"publisher","DOI":"10.1007\/b101971","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G Gutin","year":"2007","unstructured":"Gutin, G., Punnen, A.-P.: The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, Springer, London (2007)"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"de Berg, M., Bodlaender, H.-L., Kisfaludi-Bak, S., Kolay, S.: An ETH-tight exact algorithm for Euclidean TSP. In: The 59th Symposium on Foundations of Computer Science, FOCS 2018, pp. 450\u2013461. IEEE, New York (2018)","DOI":"10.1109\/FOCS.2018.00050"},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"Karlin, A.-R., Klein, N., Gharan, S.-O.: A (slightly) improved approximation algorithm for metric TSP. In: The 53rd Symposium on Theory of Computing, STOC 2021, pp. 32\u201345. ACM, New York (2021)","DOI":"10.1145\/3406325.3451009"},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2151171.2151181","volume":"8","author":"A Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms 8(2), 1\u201318 (2012)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"5_CR6","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1287\/opre.32.4.837","volume":"32","author":"R Jonker","year":"1984","unstructured":"Jonker, R., Volgenant, T.: Nonoptimal edges for the symmetric traveling salesman problem. Oper. Res. 32(4), 837\u2013846 (1984)","journal-title":"Oper. Res."},{"key":"5_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-319-12340-0_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Hougardy","year":"2014","unstructured":"Hougardy, S., Schroeder, R.T.: Edge elimination in TSP instances. In: Kratsch, D., Todinca, I. (eds.) WG 2014. LNCS, vol. 8747, pp. 275\u2013286. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-12340-0_23"},{"issue":"2","key":"5_CR8","doi-asserted-by":"publisher","first-page":"411","DOI":"10.7155\/jgaa.00400","volume":"20","author":"Y Wang","year":"2016","unstructured":"Wang, Y., Remmel, J.-B.: A binomial distribution model for travelling salesman problem based on frequency quadrilaterals. J. Graph Algorithms Appl. 20(2), 411\u2013434 (2016)","journal-title":"J. Graph Algorithms Appl."},{"issue":"1","key":"5_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R Karp","year":"1975","unstructured":"Karp, R.: On the computational complexity of combinatorial problems. Networks (USA) 5(1), 45\u201368 (1975)","journal-title":"Networks (USA)"},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Sco. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Sco. Ind. Appl. Math."},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61\u201363 (1962)","journal-title":"J. ACM"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: The 51st Symposium on Foundations of Computer Science, FOCS 2010, pp. 173\u2013182. IEEE, New York (2010)","DOI":"10.1109\/FOCS.2010.24"},{"issue":"3","key":"5_CR13","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1016\/j.ejor.2020.04.024","volume":"286","author":"Y Yuan","year":"2020","unstructured":"Yuan, Y., Cattaruzza, D., Ogier, M., Semet, F.: A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. Eur. J. Oper. Res. 286(3), 849\u2013866 (2020)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.orl.2008.09.006","volume":"37","author":"D-L Applegate","year":"2009","unstructured":"Applegate, D.-L., et al.: Certification of an optimal TSP tour through 85900 cities. Oper. Res. Lett. 37(1), 11\u201315 (2009)","journal-title":"Oper. Res. Lett."},{"key":"5_CR15","unstructured":"Cook, W.: The traveling salesman problem: postcards from the edge of impossibility (Plenary talk). In: The 30th European Conference on Operational Research, Dublin, Ireland (2019)"},{"key":"5_CR16","unstructured":"Kisfaludi-Bak, S., Nederlof, J., Wegrzycki, K.: A gap-ETH-tight approximation scheme for Euclidean TSP arXiv:2011.03778v2 (2021)"},{"issue":"1","key":"5_CR17","doi-asserted-by":"publisher","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."},{"key":"5_CR18","doi-asserted-by":"publisher","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. Discret. Algorithms 27, 1\u201320 (2014)","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s00453-015-9970-4","volume":"74","author":"M-Y Xiao","year":"2016","unstructured":"Xiao, M.-Y., Nagamochi, H.: An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure. Algorithmica 74(2), 713\u2013741 (2016). https:\/\/doi.org\/10.1007\/s00453-015-9970-4","journal-title":"Algorithmica"},{"issue":"3","key":"5_CR20","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1007\/s00453-009-9296-1","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"5_CR21","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10107-012-0620-1","volume":"144","author":"S Boyd","year":"2014","unstructured":"Boyd, S., Sitters, R., van der Ster, S., Stougie, L.: The traveling salesman problem on cubic and subcubic graphs. Math. Program. 144(1\u20132), 227\u2013245 (2014). https:\/\/doi.org\/10.1007\/s10107-012-0620-1","journal-title":"Math. Program."},{"issue":"2","key":"5_CR22","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1137\/140972925","volume":"29","author":"J-R Correa","year":"2015","unstructured":"Correa, J.-R., Larr\u00e9, O., Soto, J.-A.: TSP tours in cubic graphs: beyond 4\/3. SIAM J. Discret. Math. 29(2), 915\u2013939 (2015)","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"5_CR23","doi-asserted-by":"publisher","first-page":"1926","DOI":"10.1137\/060649562","volume":"37","author":"P Klein","year":"2008","unstructured":"Klein, P.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926\u20131952 (2008)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR24","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00453-012-9662-2","volume":"68","author":"G Borradaile","year":"2014","unstructured":"Borradaile, G., Demaine, E.-D., Tazari, S.: Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica 68(2), 287\u2013311 (2014). https:\/\/doi.org\/10.1007\/s00453-012-9662-2","journal-title":"Algorithmica"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Svensson, O., Tarnawski, J., V\u00e9gh, L.-A.: A constant-factor approximation algorithm for the asymmetric traveling salesman problem arXiv:1708.04215pdf (2019)","DOI":"10.1145\/3188745.3188824"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Traub, V., Vygen, J.: An improved approximation algorithm for ATSP. In: The 52nd Symposium on Theory of Computing, STOC 2020, pp. 1\u201313. ACM, New York (2020)","DOI":"10.1145\/3357713.3384233"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Erickson, J., Sidiropoulos, A.: A near-optimal approximation algorithm for asymmetric TSP on embedded graphs arXiv:1304.1810v2 (2013)","DOI":"10.1145\/2582112.2582136"},{"key":"5_CR28","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Sidiropoulos, A.: Polylogarithmic approximation for Euler genus on bounded degree graphs. In: The 51st Symposium on the Theory of Computing, STOC 2019, pp. 164\u2013175. ACM, New York (2019)","DOI":"10.1145\/3313276.3316409"},{"issue":"2","key":"5_CR29","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/j.ejor.2018.06.039","volume":"272","author":"E-D Taillard","year":"2019","unstructured":"Taillard, E.-D., Helsgaun, K.: POPMUSIC for the traveling salesman problem. Eur. J. Oper. Res. 272(2), 420\u2013429 (2019)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"5_CR30","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1016\/j.ejor.2006.10.062","volume":"189","author":"M Turkensteen","year":"2008","unstructured":"Turkensteen, M., Ghosh, D., Goldengorin, B., Sierksma, G.: Tolerance-based branch and bound algorithms for the ATSP. Eur. J. Oper. Res. 189(3), 775\u2013788 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"5_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-319-78455-7_22","volume-title":"Frontiers in Algorithmics","author":"Y Wang","year":"2018","unstructured":"Wang, Y., Remmel, J.: A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals. In: Chen, J., Lu, P. (eds.) FAW 2018. LNCS, vol. 10823, pp. 286\u2013299. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78455-7_22"},{"key":"5_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/978-3-030-36412-0_43","volume-title":"Combinatorial Optimization and Applications","author":"Y Wang","year":"2019","unstructured":"Wang, Y.: Bounded degree graphs computed for\u00a0traveling salesman problem based on\u00a0frequency quadrilaterals. In: Li, Y., Cardei, M., Huang, Y. (eds.) COCOA 2019. LNCS, vol. 11949, pp. 529\u2013540. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36412-0_43"},{"issue":"2","key":"5_CR33","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1007\/s10957-018-01465-9","volume":"181","author":"Y Wang","year":"2019","unstructured":"Wang, Y.: Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency qudrilaterals. J. Optim. Theory Appl. 181(2), 671\u2013683 (2019). https:\/\/doi.org\/10.1007\/s10957-018-01465-9","journal-title":"J. Optim. Theory Appl."},{"key":"5_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/978-3-030-57602-8_46","volume-title":"Algorithmic Aspects in Information and Management","author":"Y Wang","year":"2020","unstructured":"Wang, Y., Han, Z.: The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem. In: Zhang, Z., Li, W., Du, D.-Z. (eds.) AAIM 2020. LNCS, vol. 12290, pp. 513\u2013524. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-57602-8_46"},{"key":"5_CR35","series-title":"Communications in Computer and Information Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-981-15-0105-0_2","volume-title":"Theoretical Computer Science","author":"Y Wang","year":"2019","unstructured":"Wang, Y.: Special frequency quadrilaterals and an application. In: Sun, X., He, K., Chen, X. (eds.) NCTCS 2019. CCIS, vol. 1069, pp. 16\u201326. Springer, Singapore (2019). https:\/\/doi.org\/10.1007\/978-981-15-0105-0_2"}],"container-title":["Communications in Computer and Information Science","Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-19-8152-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T16:12:22Z","timestamp":1670602342000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-19-8152-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9789811981517","9789811981524"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-981-19-8152-4_5","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"type":"print","value":"1865-0929"},{"type":"electronic","value":"1865-0937"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"10 December 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"NCTCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"National Conference of Theoretical Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Changchun","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"40","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"nctcs2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.ccf.org.cn\/TCS2022","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"https:\/\/conf.ccf.org.cn\/TCS2022","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"58","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"22% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}