{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T03:11:40Z","timestamp":1772939500269,"version":"3.50.1"},"reference-count":7,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>One way to speed up the calculation of optimal traveling salesman problem tours in practice is eliminating edges that are certainly not in the optimal tour as a preprocessing step. In order to do so, several edge elimination approaches have been proposed in the past. In this work, we investigate two of them in the scenario where the input consists of n independently distributed random points in the two-dimensional unit square with density function bounded from above and below by arbitrary positive constants. We show that after the edge elimination procedure of Hougardy and Schroeder, the expected number of remaining edges is [Formula: see text], whereas after the nonrecursive part of Jonker and Volgenant, the expected number of remaining edges is [Formula: see text].<\/jats:p>","DOI":"10.1287\/moor.2020.0299","type":"journal-article","created":{"date-parts":[[2025,3,20]],"date-time":"2025-03-20T13:40:21Z","timestamp":1742478021000},"page":"621-640","source":"Crossref","is-referenced-by-count":0,"title":["Probabilistic Analysis of Edge Elimination for Euclidean TSP"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3812-2903","authenticated-orcid":false,"given":"Xianghui","family":"Zhong","sequence":"first","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, 53113 Bonn, Germany"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9801-4"},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Garey MR, Graham RL, Johnson DS (1976) Some NP-complete geometric problems.\n                      Proc. Eighth Annu. ACM Sympos. Theory Comput. STOC\u201976\n                      (Association for Computing Machinery, New York), 10\u201322.","DOI":"10.1145\/800113.803626"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12340-0_23"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.4.837"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90012-3"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2020.0299","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T09:40:41Z","timestamp":1772876441000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2020.0299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1287\/moor.2020.0299"],"URL":"https:\/\/doi.org\/10.1287\/moor.2020.0299","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1]]}}}