On approximation problems related to the independent set and vertex cover problems (Q760210): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
| links / mardi / name | links / mardi / name | ||
Revision as of 10:26, 30 January 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On approximation problems related to the independent set and vertex cover problems |
scientific article |
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
