A Probability Model Based on Frequency Quadrilaterals for Travelling Salesman Problem

DOI

10.2991/amsm-16.2016.7How to use a DOI?

Keywords

travelling salesman problem; sparse graph; probability model; frequency quadrilateral; optimal i-vertex path

Abstract

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.

Copyright

© 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/).

Download article (PDF)

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  -