A note on the approximability of the toughness of graphs

DOI10.1016/J.DISC.2003.10.013zbMATH Open1041.05070OpenAlexW2038001771MaRDI QIDQ1827680FDOQ1827680

Authors: Cristina Bazgan 

Publication date: 6 August 2004

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2003.10.013

Recommendations

• On the complexity of recognizing tough graphs
• Toughness, hamiltonicity and split graphs
• Recognizing tough graphs is NP-hard
• The complexity of recognizing minimally tough graphs
• The toughness of split graphs

zbMATH Keywords

ComplexityApproximation algorithmGraphToughness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• On the hardness of approximating minimization problems
• Tough graphs and Hamiltonian circuits.
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Recognizing tough graphs is NP-hard

Cited In (4)

• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• Results on toughness in graphs under heavy subgraph conditions
• An efficient algorithm to compute the toughness in graphs with bounded treewidth
• The toughness of split graphs

This page was built for publication: A note on the approximability of the toughness of graphs

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