سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات161
تعداد شماره‌ها6,532
تعداد مقالات70,500
تعداد مشاهده مقاله124,091,129
تعداد دریافت فایل اصل مقاله97,195,079
Swart, E. R., Gismondi, Stephen J., Swart, N. R., Bell, C. E., Lee, A.. (1395). Deciding Graph non-Hamiltonicity via a Closure Algorithm. , 48(1), 1-35. doi: 10.22059/jac.2016.7937
E. R. Swart; Stephen J. Gismondi; N. R. Swart; C. E. Bell; A. Lee. "Deciding Graph non-Hamiltonicity via a Closure Algorithm". , 48, 1, 1395, 1-35. doi: 10.22059/jac.2016.7937
Swart, E. R., Gismondi, Stephen J., Swart, N. R., Bell, C. E., Lee, A.. (1395). 'Deciding Graph non-Hamiltonicity via a Closure Algorithm', , 48(1), pp. 1-35. doi: 10.22059/jac.2016.7937
Swart, E. R., Gismondi, Stephen J., Swart, N. R., Bell, C. E., Lee, A.. Deciding Graph non-Hamiltonicity via a Closure Algorithm. , 1395; 48(1): 1-35. doi: 10.22059/jac.2016.7937

Deciding Graph non-Hamiltonicity via a Closure Algorithm

Journal of Algorithms and Computation
مقاله 1، دوره 48، شماره 1، اسفند 2016، صفحه 1-35    اصل مقاله (438.29 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2016.7937
نویسندگان
E. R. Swart1؛ Stephen J. Gismondi* 2؛ N. R. Swart3؛ C. E. Bell4؛ A. Lee2
1Kelowna, British Columbia, Canada
2University of Guelph, Canada
3University of British Columbia Okanagan, Canada
4Guelph, Ontario, Canada
چکیده
We present a matching and LP based heuristic algorithm that decides graph non-Hamiltonicity. Each of the n! Hamilton cycles in a complete directed graph on n + 1 vertices corresponds with each of the n! n-permutation matrices P, such that pu,i = 1 if and only if the ith arc in a cycle enters vertex u, starting and ending at vertex n + 1. A graph instance (G) is initially coded as exclusion set E, whose members are pairs of components of P, {pu,i, pv,i+1}, i = 1, n - 1, for each arc (u, v) not in
کلیدواژه‌ها
Hamilton cycle؛ decision problem
آمار
تعداد مشاهده مقاله: 1,323
تعداد دریافت فایل اصل مقاله: 1,083


سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب