• Home
  • Browse
    • Current Issue
    • By Issue
    • By Author
    • By Subject
    • Author Index
    • Keyword Index
  • Journal Info
    • About Journal
    • Aims and Scope
    • Editorial Board
    • Advisory Board
    • Editorial Staff
    • Publication Ethics
    • Indexing and Abstracting
    • Related Links
    • FAQ
    • Peer Review Process
    • News
  • Guide for Authors
  • Submit Manuscript
  • Reviewers
  • Contact Us
 
  • Login
  • Register
Home Articles List Article Information
  • Save Records
  • |
  • Printable Version
  • |
  • Recommend
  • |
  • How to cite Export to
    RIS EndNote BibTeX APA MLA Harvard Vancouver
  • |
  • Share Share
    CiteULike Mendeley Facebook Google LinkedIn Twitter Telegram
Transactions on Combinatorics
Articles in Press
Current Issue
Journal Archive
Volume Volume 7 (2018)
Volume Volume 6 (2017)
Volume Volume 5 (2016)
Volume Volume 4 (2015)
Volume Volume 3 (2014)
Volume Volume 2 (2013)
Volume Volume 1 (2012)
Issue Issue 4
Issue Issue 3
Issue Issue 2
Issue Issue 1
Cvetković, D. (2012). Complexity indices for the travelling salesman problem and data mining. Transactions on Combinatorics, 1(1), 35-43. doi: 10.22108/toc.2012.723
Dragos Cvetković. "Complexity indices for the travelling salesman problem and data mining". Transactions on Combinatorics, 1, 1, 2012, 35-43. doi: 10.22108/toc.2012.723
Cvetković, D. (2012). 'Complexity indices for the travelling salesman problem and data mining', Transactions on Combinatorics, 1(1), pp. 35-43. doi: 10.22108/toc.2012.723
Cvetković, D. Complexity indices for the travelling salesman problem and data mining. Transactions on Combinatorics, 2012; 1(1): 35-43. doi: 10.22108/toc.2012.723

Complexity indices for the travelling salesman problem and data mining

Article 6, Volume 1, Issue 1, March 2012, Page 35-43  XML PDF (437 K)
Document Type: Research Paper
DOI: 10.22108/toc.2012.723
Author
Dragos Cvetković
Abstract
 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.
Keywords
Travelling Salesman Problem; Spectral clustering algorithms; Hamiltonian cycle
Main Subjects
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.); 90C27 Combinatorial optimization
References
B. Ashok and T.K. Patra (2010). Locating phase transitions in computationally hard problems. J. Physics, to appear.
D. Cvetkovi' c, M. v Cangalovi' c and V. Kovav cevi' c-Vujv ci' c (1999). Semidefinite programming methods for the symmetric travelling salesman problem. Integer Programming and Combinatorial Optimization, Proc. 7th Internat. IPCO Conf.Graz, Austria, June 1999, Lecture Notes Comp. Sci. 1610, Springer, Berlin. , 126-136
D. Cvetkovi' c, M. v Cangalovi' c and V. Kovav cevi' c-Vujv ci' c (1999). Complexity indices for the travelling salesman problem based on a semidefinite relaxation. SYM-OP-IS '99, Proc. XXVI Yugoslav Symp. Operations Research, Beograd. , 177-180
D. Cvetkovi' c, M. v Cangalovi' c and V. Kovav cevi' c-Vujv ci' c (2004). Optimization and highly informative graph invariants. Two Topics in Mathematics, ed. B.Stankovi' c, Zbornik radova 10(18), Matemativ cki institut SANU, Beograd. , 5-39
D. Cvetkovi'c, P. Rowlinson and S. K. Simi'c (2009). An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge.
D. Cvetkovi' c and S.K. Simi' c (2011). Graph spectra in computer science. Linear Algebra Appl.. 434, 1545-1562
M. Fiedler (1973). Algebraic connectivity of graphs. Czech. J. Math.. 23 (98), 298-305
G. Gutin and A. Punnen (2002). The Travelling Salesman Problem and Its Variations. Kluwer Academic Publishers, Dordrecht.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan and D.B. Shmoys (1985). The Traveling Salesman Problem. John Wiley and Sons, Chichester - New York - Brisbane - Toronto - Singapore.
K. Ko, P. Orponen, U. Sch" oning and O. Watanabe (1986). What is a hard instance of a computational problem ?. Structure in Complexity Theory. Conf. 1986, Lecture Notes in Computer Science, Springer. , 197-217
U. von Luxburg (2007). A tutorial on spectral clustering. Stat. Comput.. 17, 395-416
C.R. Reeves and A.V. Eremeev (2004). Statistical analysis of local search landscapes. J. Oper. Res. Soc.. 55, 687-693
B.D. Reyck and W. Herroelen (1996). On the use of the complexity index as a measure of complexity in activity networks. Europ. J. Oper. Res.. 91, 347-366
R. Sawilla (2008). A survey of data mining of graphs using spectral graph theory. Defence R&D Canada, Ottawa, Technical Memorandum TM 2008-317, Ottawa.
Statistics
Article View: 4,765
PDF Download: 3,063
Home | Glossary | News | Aims and Scope | Sitemap
Top Top

Journal Management System. Designed by sinaweb.