On approximation problems related to the independent set and vertex cover problems (Q760210): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 01:09, 5 March 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
