Recognizing tough graphs is NP-hard
From MaRDI portal
Publication:918697
DOI10.1016/0166-218X(90)90001-SzbMATH Open0706.68052DBLPjournals/dam/BauerHS90OpenAlexW1981583245WikidataQ61248964 ScholiaQ61248964MaRDI QIDQ918697FDOQ918697
Authors: D. Bauer, S. Louis Hakimi, E. Schmeichel 
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(90)90001-s
Recommendations
- On the complexity of recognizing tough graphs
- Recognizing tenacious graphs is NP-hard.
- The complexity of recognizing minimally tough graphs
- NP-hardness of the recognition of coordinated graphs
- Recognizing graphs with fixed interval number is NP-complete
- The complexity of recognizing tough cubic graphs
- Clique Graph Recognition Is NP-Complete
- Unit disk graph recognition is NP-hard
- Point visibility graph recognition is NP-hard
- Discontinuities in the complexities of some graph recognition problems
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Cites Work
Cited In (49)
- An efficient algorithm to compute the toughness in graphs with bounded treewidth
- Node and link vulnerability in complete multipartite networks
- Better approximations of non-Hamiltonian graphs
- Toughness in graphs -- a survey
- Computing the binding number of a graph
- Title not available (Why is that?)
- Graph invariants and large cycles: a survey
- The complexity of recognizing minimally tough graphs
- Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
- Toughness and binding number
- Approximation and kernelization for chordal vertex deletion
- The complexity of recognizing tough cubic graphs
- A note on dominating cycles in 2-connected graphs
- On one extension of Dirac's theorem on Hamiltonicity
- Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
- 1-tough cocomparability graphs are hamiltonian
- A brief account on the development and future research directions of connectivity properties of interconnection networks
- A note on the link residual closeness of graphs under join operation
- Bipartite toughness and \(k\)-factors in bipartite graphs
- The scattering number of strictly chordal graphs: linear time determination
- Recognition of split-graphic sequences
- Recognizing tenacious graphs is NP-hard.
- Link vulnerability in networks
- Toughness and Delaunay triangulations
- Title not available (Why is that?)
- Title not available (Why is that?)
- A polynomial algorithm for weighted scattering number in interval graphs
- On the toughness index of planar graphs
- The toughness of split graphs
- Measuring the vulnerability for classes of intersection graphs
- Characterization of 1-tough graphs using factors
- Toughness, binding number and restricted matching extension in a graph
- String graphs. II: Recognizing string graphs is NP-hard
- Computational complexity of network vulnerability analysis
- Approximation of coNP sets by NP-complete sets
- Best monotone degree conditions for graph properties: a survey
- An upper bound on the shortness exponent of 1-tough, maximal planar graphs
- Toughness of the corona of two graphs
- Computing the Scattering Number of Graphs
- Maximum and minimum toughness of graphs of small genus
- On the complexity of recognizing tough graphs
- Fixed edge-length graph drawing is NP-hard
- Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness
- Toughness, hamiltonicity and split graphs
- A note on the approximability of the toughness of graphs
- A large set of non-Hamiltonian graphs
- The vertex attack tolerance of complex networks
- On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
- Chvátal's \(t_{0}\)-tough conjecture
This page was built for publication: Recognizing tough graphs is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q918697)
