پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,225 |
| تعداد مقالات | 67,685 |
| تعداد مشاهده مقاله | 115,001,408 |
| تعداد دریافت فایل اصل مقاله | 89,679,894 |
On the Minimum of True Matches in Exact Graph Matching with Simulated Annealing | ||
| Journal of Algorithms and Computation | ||
| دوره 53، شماره 1، شهریور 2021، صفحه 123-134 اصل مقاله (438.49 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2021.81628 | ||
| نویسندگان | ||
| Hashem Ezzati1؛ Mahmood Amintoosi* 2؛ Hashem Tabasi3 | ||
| 1Department of Computer Science, Amir Kabir University of Technology, Tehran, Iran | ||
| 2Faculty of Mathematics and Computer science, Hakim Sabzevari University, Sabzevar, Iran | ||
| 3Department of Computer Science, Damghan University | ||
| چکیده | ||
| Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard and NP-Complete problems, but for graph matching problem, there were not reported superior solutions by these sort of algorithms. The reason of this inefficiency has not been investigated yet. In this paper it has been shown that Simulated Annealing (SA) as an instance of a meta-heuristic method is unlikely to be even close to the optimal solution for this problem. Mathematical and experimental results showed that the chance to reach to a partial solution, is very low, even for small number of true matches. In addition to theoretical discussion, the experimental results also verified our idea; for example, in two sample graphs with $10000$ vertices, the probability of reaching to a solution with at least three correct matches is about $0.02$ with simulated annealing. | ||
| کلیدواژه‌ها | ||
| Graph matching؛ Simulated Annealing؛ Meta-Heuristic؛ Stochastic Optimization | ||
|
آمار تعداد مشاهده مقاله: 310 تعداد دریافت فایل اصل مقاله: 150 |
||