The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems (Q1356067): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1023/a:1008660812834 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1539745397 / rank | |||
Normal rank | |||
Latest revision as of 09:16, 30 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems |
scientific article |
Statements
The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems (English)
0 references
4 June 1997
0 references
NP-complete problem
0 references
independent set
0 references
polynomial time \(\rho\)-approximation algorithm
0 references
vertex covering
0 references
quadratic programming as subproblem
0 references
