Better approximations of non-Hamiltonian graphs (Q1382268)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1133164
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Better approximations of non-Hamiltonian graphs |
scientific article; zbMATH DE number 1133164 |
Statements
Better approximations of non-Hamiltonian graphs (English)
0 references
2 June 1998
0 references
The problem of recognizing the class of non-sub-2-factor graphs (NS2F) is established to be NP-complete. Another proof of an earlier result about NP-ompleteness for the class of non-1-tough graphs (N1T) is also given. Both classes may have applications in generating, in polynomial time, random non-Hamiltonian graphs. In this paper it is argued that the class NS2F is substantially larger than the class N1T (the difference is a \(\text{D}^P\)-complete set) and, thus, is more suitable for the task of random generation of instances of non-Hamiltonian graphs.
0 references
NP-ompleteness
0 references
non-Hamiltonian graphs
0 references
0.9098102
0 references
0.8925574
0 references
0.88382703
0 references
0 references
0.87320745
0 references
0.87166905
0 references
0.87166905
0 references
0.87045693
0 references
0 references
