The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover
Copyright policy )The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover
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.
- RWTH Aachen University Germany
- Institute of Mathematical Sciences India
- Indian Institutes of Technology India
unique game conjecture, Analysis of algorithms and problem complexity, vertex cover, König vertex/edge deletion sets, maximum matching, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), König graphs, Graph algorithms (graph-theoretic aspects), above guarantee vertex cover, approximation algorithms, parameterized complexity
unique game conjecture, Analysis of algorithms and problem complexity, vertex cover, König vertex/edge deletion sets, maximum matching, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), König graphs, Graph algorithms (graph-theoretic aspects), above guarantee vertex cover, approximation algorithms, parameterized complexity
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).24 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!