|
gptkbp:instanceOf
|
Graph Theory Concept
|
|
gptkbp:approximationAlgorithm
|
2-approximation algorithm exists
|
|
gptkbp:approximationRatio
|
2
|
|
gptkbp:category
|
gptkb:Graph_Algorithms
gptkb:Combinatorial_Optimization
Computational Complexity
|
|
gptkbp:complement
|
gptkb:Maximum_Independent_Set
|
|
gptkbp:complexity
|
Fixed-parameter tractable
|
|
gptkbp:decision
|
Does a graph have a vertex cover of size k?
|
|
gptkbp:decisionProblemComplexity
|
NP-complete
|
|
gptkbp:definedIn
|
A set of vertices such that every edge in the graph is incident to at least one vertex in the set
|
|
gptkbp:firstDescribed
|
gptkb:König,_1931
|
|
gptkbp:hasSpecialCase
|
gptkb:Bipartite_Graphs
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Vertex Cover
|
|
gptkbp:input
|
gptkb:Undirected_Graph
|
|
gptkbp:minimumVertexCover
|
Smallest possible vertex cover in a graph
|
|
gptkbp:NP-complete
|
Yes
|
|
gptkbp:optimizationProblem
|
Find the minimum vertex cover
|
|
gptkbp:output
|
Set of vertices
|
|
gptkbp:polynomialTimeSolvable
|
Yes, for bipartite graphs
|
|
gptkbp:relatedTo
|
gptkb:Dominating_Set
gptkb:Edge_Cover
Independent Set
|
|
gptkbp:supportsAlgorithm
|
gptkb:Branch_and_Bound
gptkb:Greedy_Algorithm
gptkb:König's_Theorem
gptkb:Linear_Programming_Relaxation
|
|
gptkbp:usedIn
|
gptkb:Bioinformatics
Network Security
Resource Allocation
|
|
gptkbp:bfsParent
|
gptkb:Karp's_21_NP-complete_problems
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
|
|
gptkbp:bfsLayer
|
6
|