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

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

 آمار

تعداد نشریات158
تعداد شماره‌ها6,230
تعداد مقالات67,758
تعداد مشاهده مقاله115,127,194
تعداد دریافت فایل اصل مقاله89,895,387
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,250
تعداد دریافت فایل اصل مقاله: 1,043


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