On approximation problems related to the independent set and vertex cover problems (Q760210)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On approximation problems related to the independent set and vertex cover problems |
scientific article; zbMATH DE number 3883606
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On approximation problems related to the independent set and vertex cover problems |
scientific article; zbMATH DE number 3883606 |
Statements
On approximation problems related to the independent set and vertex cover problems (English)
0 references
1984
0 references
Some open questions concerning the complexity of approximation algorithms for the Maximum Independent Set and Minimum Vertex Cover Problems are studied. It is shown that those questions are at least as hard as a sample of other open questions concerning approximating NP-hard problems, including Graph Coloring, Set Covering and Dominating Set Problems.
0 references
complexity of approximation algorithms
0 references
Maximum Independent Set
0 references
Minimum Vertex Cover
0 references
0.8332903981208801
0 references
0.8327471017837524
0 references
0.8326666951179504
0 references
0.8316939473152161
0 references
0.8185615539550781
0 references
