Hard graphs for the maximum clique problem

Share/Save/Bookmark

Hoede, Cornelis (1988) Hard graphs for the maximum clique problem. Discrete Mathematics, 72 (1-3). pp. 175-179. ISSN 0012-365X

open access
[img]
Preview
PDF
273kB
Abstract:The maximum clique problem is one of the NP-complete problems. There are graphs for which a reduction technique exists that transforms the problem for these graphs into one for graphs with specific properties in polynomial time. The resulting graphs do not grow exponentially in order and number. Graphs that allow such a reduction technique are called soft. Hard graphs are those graphs for which none of the reduction techniques can be applied. A list of properties of hard graphs is determined.
Item Type:Article
Copyright:© 1988 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Link to this item:http://purl.utwente.nl/publications/70038
Official URL:http://dx.doi.org/10.1016/0012-365X(88)90207-5
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page