Xamilton yakunlandi - Hamiltonian completion

The Xamilton yakunlandi muammo, a ga qo'shiladigan minimal sonli qirralarni topishdir grafik buni amalga oshirish Hamiltoniyalik.

Muammo aniq Qattiq-qattiq umuman olganda (chunki uning echimi. ga javob beradi To'liq emas berilgan grafikada a mavjudligini aniqlash muammosi Gamilton tsikli ). Bilan bog'liq qaror muammosi yoki yo'qligini aniqlash K Berilgan grafaga qirralar qo'shilib, Gamilton grafigi NP bilan to'ldirilgan bo'lishi mumkin.

Bundan tashqari, Xamiltonning yakunlanishi quyidagilarga tegishli APX murakkablik sinfi, ya'ni bu unchalik samarali bo'lishi ehtimoldan yiroq emas doimiy nisbati yaqinlashishi algoritmlari ushbu muammo uchun mavjud.[1]

Muammo hal qilinishi mumkin polinom vaqti ba'zi bir grafikalar sinflari uchun, shu jumladan ketma-ket parallel grafikalar[2] va ularni umumlashtirish,[3] o'z ichiga oladi tashqi planli grafikalar, shuningdek, a chiziqli grafik daraxt[4][5]yoki a kaktus grafigi.[6]

Gamarnik va boshq. siyrak uchun qo'shilishi kerak bo'lgan asimptotik sonlarni o'rganish uchun daraxtlardagi muammoni hal qilish uchun chiziqli vaqt algoritmidan foydalaning tasodifiy grafikalar ularni Hamiltoniyalik qilish.[7]

Adabiyotlar

  1. ^ Q. S. Vu, C. L. Lu, R. C. T. Li, Daraxtda og'ir vaznli Hamilton yo'lini bajarish masalasi uchun taxminiy algoritm, Kompyuter fanidan ma'ruza matnlari, Jild 1969 (2000) Sahifalar: 156 - 167
  2. ^ Takamizava, K .; Nishizeki, T.; Saito, N. (1982), "Kombinatorial masalalarni ketma-ket parallel grafiklarda chiziqli vaqt ichida hisoblash", ACM jurnali, 29 (3): 623–641, doi:10.1145/322326.322328.
  3. ^ N. M. Korneyenko, grafikalar klassi bo'yicha kombinator algoritmlar, Diskret amaliy matematika, v.54 ​​n.2-3, s.215-217, 1994 y
  4. ^ Arundhati Raychaudhuri, Daraxtning umumiy intervalli raqami va uning chiziqli grafilining gamiltoncha tugash raqami, Axborotni qayta ishlash xatlari, 56-jild, 6-son (1995 yil dekabr) 299 - 306
  5. ^ A. Agnetis, P. Detti, C. Meloni, D. Pakciarelli, Daraxtning chiziqli grafigining gamiltoncha yakunlanish raqami uchun chiziqli algoritm, Axborotni qayta ishlash xatlari, 79-jild, 1-son (2001 yil may), 17-24
  6. ^ Paolo Detti, Karlo Meloni, Kaktusning chiziqli grafilining gamiltoncha yakunlash raqami uchun chiziqli algoritm, Diskret amaliy matematik, 136-jild, 2-3-son (2004 yil fevral) 197 - 215
  7. ^ Devid Gamarnik, Maksim Sviridenko, Siyrak tasodifiy grafiklarning gamiltoncha yakunlari, Diskret amaliy matematika 152 (2005) 139 - 158