The complexity of König subgraph problems and above-guarantee vertex cover (Q652520): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 09:50, 30 January 2024

scientific article
Language Label Description Also known as
English
The complexity of König subgraph problems and above-guarantee vertex cover
scientific article

    Statements

    The complexity of König subgraph problems and above-guarantee vertex cover (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    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

    Identifiers