Complexity indices for the travelling salesman problem and data mining
Publish place: Transactions on Combinatorics، Vol: 1، Issue: 1
Publish Year: 1391
نوع سند: مقاله ژورنالی
زبان: English
View: 106
This Paper With 9 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
این Paper در بخشهای موضوعی زیر دسته بندی شده است:
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_COMB-1-1_006
تاریخ نمایه سازی: 29 آبان 1400
Abstract:
we extend our previous work on complexity indices for the travelling salesman problem (TSP), summarized in cite{CvCK۳}, 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.
Authors
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :