TY - JOUR ID - 79270 TI - A note on the approximability of the tenacity of graphs JO - Journal of Algorithms and Computation JA - JAC LA - en SN - 2476-2776 AU - Heidari, Vahid AU - Moazzami, Dara AD - University of Tehran, Department of Algorithms and Computation. AD - University of Tehran, College of Engineering, Faculty of Engineering Science Y1 - 2020 PY - 2020 VL - 52 IS - 2 SP - 149 EP - 157 KW - $NP$-complete problem KW - Tenacity KW - Tenacious KW - $NP$-hard DO - 10.22059/jac.2020.79270 N2 - In this paper we show that, if $NP\neq ZPP$, for any $\epsilon > 0$, the tenacity of graphwith $n$ vertices is not approximable in polynomial time within a factor of$\frac{1}{2} \left( \frac{n-1}{2} \right) ^{1-\epsilon}$. UR - https://jac.ut.ac.ir/article_79270.html L1 - https://jac.ut.ac.ir/article_79270_0a4d1e9aa72c099beb4fcfe521d1bc23.pdf ER -