میز خدمت الکترونیک
دوره ویراستاری

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

 آمار

تعداد نشریات126
تعداد شماره‌ها7,103
تعداد مقالات76,310
تعداد مشاهده مقاله151,990,192
تعداد دریافت فایل اصل مقاله113,964,275
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,459
تعداد دریافت فایل اصل مقاله: 1,214





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