The complexity of König subgraph problems and above-guarantee vertex cover (Q652520)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5988465
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The complexity of König subgraph problems and above-guarantee vertex cover |
scientific article; zbMATH DE number 5988465 |
Statements
The complexity of König subgraph problems and above-guarantee vertex cover (English)
0 references
14 December 2011
0 references
A graph is called König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been extensively studied from a graph-theoretic point of view. The authors introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. They show that different problems in this context are NP-complete.
0 references
vertex cover
0 references
above guarantee vertex cover
0 references
König graphs
0 references
König vertex/edge deletion sets
0 references
maximum matching
0 references
parameterized complexity
0 references
approximation algorithms
0 references
unique game conjecture
0 references
0 references
0 references
0 references
0.946677565574646
0 references
0.8872530460357666
0 references
0.8525155186653137
0 references
0.8450219035148621
0 references
0.8158189058303833
0 references
