A note on the approximability of the toughness of graphs

DOI10.1016/j.disc.2003.10.013zbMath1041.05070OpenAlexW2038001771MaRDI QIDQ1827680

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

zbMATH Keywords

ComplexityApproximation algorithmGraphToughness

Mathematics Subject Classification ID

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

Cites Work

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

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