A note on the approximability of the tenacity of graphs
نویسندگان
1 University of Tehran, Department of Algorithms and Computation.
2 University of Tehran, College of Engineering, Faculty of Engineering Science.
doi
10.22059/jac.2020.79270چکیده
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}$.
