Abstract
The inapproximability results of Maxclique, chromatic number and graph coloring were examined. The results on the problem of finding the size of largest clique and chromatic number in a graph were obtained by the PCP constructions based on Hadamard codes. The polynomial time approximation algorithm for Maxclique achieves an approximation ratio which suggests that the problem is hard to approximate. The approximate graph coloring was shown to be NP-hard for all sufficiently large color constants values.
| Original language | English (US) |
|---|---|
| Title of host publication | Annual Symposium on Foundations of Computer Science - Proceedings |
| Pages | 600-609 |
| Number of pages | 10 |
| State | Published - 2001 |
| Event | 42nd Annual Symposium on Foundations of Computer Science - Las Vegas, NV, United States Duration: Oct 14 2001 → Oct 17 2001 |
Other
| Other | 42nd Annual Symposium on Foundations of Computer Science |
|---|---|
| Country/Territory | United States |
| City | Las Vegas, NV |
| Period | 10/14/01 → 10/17/01 |
ASJC Scopus subject areas
- Hardware and Architecture