A note on the approximability of the toughness of graphs

DOI10.1016/J.DISC.2003.10.013MaRDI QIDQ1827680zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

ComplexityApproximation algorithmGraphToughness

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(4)

• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• An efficient algorithm to compute the toughness in graphs with bounded treewidth
• Results on toughness in graphs under heavy subgraph conditions
• 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)