On the algorithmic complexity of twelve covering and independence parameters of graphs (Q1283793)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the algorithmic complexity of twelve covering and independence parameters of graphs |
scientific article |
Statements
On the algorithmic complexity of twelve covering and independence parameters of graphs (English)
0 references
31 May 1999
0 references
Twelve parameters related to covering of vertices and/or edges by vertices and/or edges, and to independence, are identified in a uniform framework. Known results on these parameters are surveyed, focusing on complexity results. Several new NP-completeness results are established.
0 references
edge covering
0 references
vertex covering
0 references
matching
0 references
independence
0 references
0 references
