Recognizing tenacious graphs is NP-hard.

zbMATH Open1340.05144MaRDI QIDQ5502385FDOQ5502385

Authors: Seyed Morteza Dadvand, Dara Moazzami, Ali Moeini 

Publication date: 26 August 2015

Recommendations

• scientific article; zbMATH DE number 6770058
• Tenacity and the maximum network
• Recognizing tough graphs is NP-hard
• scientific article; zbMATH DE number 861347
• Computing the tenacity of some graphs

zbMATH Keywords

NP-completenessvulnerabilitytenacity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38) Connectivity (05C40)

Cited In (5)

• On the first-order edge tenacity of a graph
• Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time
• Title not available (Why is that?)
• Recognizing tough graphs is NP-hard
• On the complexity of recognizing tough graphs

This page was built for publication: Recognizing tenacious graphs is NP-hard.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502385)