On the algorithmic complexity of twelve covering and independence parameters of graphs (Q1283793)
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 the algorithmic complexity of twelve covering and independence parameters of graphs |
scientific article; zbMATH DE number 1271071
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the algorithmic complexity of twelve covering and independence parameters of graphs |
scientific article; zbMATH DE number 1271071 |
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
