TY - JOUR
ID - 723
TI - Complexity indices for the travelling salesman problem and data mining
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Cvetković, Dragos
AD -
Y1 - 2012
PY - 2012
VL - 1
IS - 1
SP - 35
EP - 43
KW - Travelling Salesman Problem
KW - Spectral clustering algorithms
KW - Hamiltonian cycle
DO - 10.22108/toc.2012.723
N2 - we extend our previous work on complexity indices for the travelling salesman problem (TSP), summarized in cite{CvCK3}, using graph spectral techniques of data mining. A complexity index is an invariant of an instance $I$ by which we can predict the execution time of an exact algorithm for TSP for $I$. We consider the symmetric travelling salesman problem with instances $I$ represented by complete graphs $G$ with distances between vertices (cities) as edge weights (lengths). Intuitively, the hardness of an instance $G$ depends on the distribution of short edges within $G$. Therefore we consider some short edge subgraphs of $G$ (minimal spanning tree, critical connected subgraph, and several others) as non-weighted graphs and several their invariants as potential complexity indices. Here spectral invariants (e.g. spectral radius of the adjacency matrix) play an important role since, in general, there are intimate relations between eigenvalues and the structure of a graph. Since hidden details of short edge subgraphs really determine the hardness of the instance, we use techniques of data mining to find them. In particular, spectral clustering algorithms are used including information obtained from the spectral gap in Laplacian spectra of short edge subgraphs.
UR - https://toc.ui.ac.ir/article_723.html
L1 - https://toc.ui.ac.ir/article_723_a83c593b06f18b6cdb9a9a465d56305d.pdf
ER -