A Probability Model Based on Frequency Quadrilaterals for Travelling Salesman Problem
- 10.2991/amsm-16.2016.7How to use a DOI?
- travelling salesman problem; sparse graph; probability model; frequency quadrilateral; optimal i-vertex path
The research aims to generate a sparse graph for travelling salesman problem so as to reduce its complexity. A probability model based on frequency quadrilaterals is given to show that the average frequency of an edge is 3N if its total frequency is computed with N random frequency quadrilaterals in complete graph K_n. For an edge in the optimal Hamiltonian cycle, the minimum frequency is derived as (3+2/(n-2))N.It suggests we can throw away the edges with frequency below (3+2/(n-2))N and still keep the optimal Hamiltonian cycle in the reserved graph. We test the probability model with quitea few Euclidean TSP instances. The results show the threshold(3+2/(n-2))Nis too small for most of the instances.
- © 2016, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Peter Yong Wang PY - 2016/05 DA - 2016/05 TI - A Probability Model Based on Frequency Quadrilaterals for Travelling Salesman Problem BT - Proceedings of the 2016 International Conference on Applied Mathematics, Simulation and Modelling PB - Atlantis Press SP - 28 EP - 31 SN - 2352-538X UR - https://doi.org/10.2991/amsm-16.2016.7 DO - 10.2991/amsm-16.2016.7 ID - Wang2016/05 ER -