Recognizing Tenacious Graphs is $NP$-Hard

Dadvand, Seyed; Moazzami, Dara; Moeini, Ali

Abstract

References

Ars Combinatoria

Volume 115
Pages: 163-174

Research article

Recognizing Tenacious Graphs is $N P$ -Hard

^¹, ^²,³, ^²

¹ University of Tehran, School of Engineering, Faculty of Engineering Science, Department of Algorithms and Computation, Tehran, Iran

²University of Tehran, School of Engineering, Faculty of Engineering Science, Department of Algorithms and Computation, Tehran, Iran

³University of California Los Angeles, (UCLA), Department of Mathematics, U.S.A.

Published: 31/07/2014

Download PDF
Cite

Copyright Link
License

Abstract

In this paper we settle a long-standing open problem. We prove that it
is $N P$ -hard to recognize $T$ -tenacious graphs for any fixed positive rational
number $T$

Contents

Ars Combinatoria

Recognizing Tenacious Graphs is $N P$ -Hard

Abstract

Information

Guidelines

CP Initiatives

Follow CP

Contents

Ars Combinatoria

Recognizing Tenacious Graphs is NP-Hard

Abstract

Information

Guidelines

CP Initiatives

Follow CP

Recognizing Tenacious Graphs is $N P$ -Hard