پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 158 |
| تعداد شماره‌ها | 6,230 |
| تعداد مقالات | 67,764 |
| تعداد مشاهده مقاله | 115,146,951 |
| تعداد دریافت فایل اصل مقاله | 89,907,918 |
A note on the approximability of the tenacity of graphs | ||
| Journal of Algorithms and Computation | ||
| دوره 52، شماره 2، اسفند 2020، صفحه 149-157 اصل مقاله (264.1 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22059/jac.2020.79270 | ||
| نویسندگان | ||
| Vahid Heidari1؛ Dara Moazzami* 2 | ||
| 1University of Tehran, Department of Algorithms and Computation. | ||
| 2University of Tehran, College of Engineering, Faculty of Engineering Science | ||
| چکیده | ||
| In this paper we show that, if $NP\neq ZPP$, for any $\epsilon > 0$, the tenacity of graph with $n$ vertices is not approximable in polynomial time within a factor of $\frac{1}{2} \left( \frac{n-1}{2} \right) ^{1-\epsilon}$. | ||
| کلیدواژه‌ها | ||
| $NP$-complete problem؛ tenacity؛ tenacious؛ $NP$-hard | ||
|
آمار تعداد مشاهده مقاله: 185 تعداد دریافت فایل اصل مقاله: 149 |
||