Title of article :
A note on the approximability of the tenacity of graphs
Author/Authors :
Heidari, Vahid Department of Algorithms and Computation - University of Tehran , Moazzami, Dara College of Engineering - University of Tehran
Abstract :
In this paper we show that, if NP≠ZPP, for any ϵ>0, the tenacity of graph
with n vertices is not approximable in polynomial time within a factor of
12(n−12)1−ϵ.
Keywords :
NP-complete problem , tenacity , tenacious , NP -hard
Journal title :
Journal of Algorithms and Computation
