Statements (39)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Graph Theory Concept
|
| gptkbp:alsoKnownAs |
gptkb:Vertex_Cover
|
| gptkbp:appliesTo |
Directed Graphs
Undirected Graphs |
| gptkbp:approximationAlgorithm |
2-approximation algorithm exists
|
| gptkbp:complementIs |
Independent Set
|
| gptkbp:complexity |
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:describedBy |
gptkb:Karp's_21_NP-complete_problems
|
| gptkbp:firstDescribed |
1972
|
| gptkbp:hasParameterizedComplexity |
Fixed-parameter tractable for small cover size
|
| gptkbp:hasSubgroup |
Vertices of the Graph
|
| https://www.w3.org/2000/01/rdf-schema#label |
Node Cover
|
| gptkbp:inBipartiteGraphs |
Minimum node cover equals maximum matching (König's theorem)
|
| gptkbp:minimumNodeCover |
Smallest possible node cover for a given graph
|
| gptkbp:minimumNodeCoverProblem |
NP-complete
|
| gptkbp:minimumNodeCoverSize |
At least the size of the maximum matching
|
| gptkbp:relatedTo |
gptkb:Clique
gptkb:Edge_Cover Independent Set |
| gptkbp:solvedBy |
gptkb:Integer_Linear_Programming
gptkb:Branch_and_Bound Greedy Algorithms Approximation Algorithms |
| gptkbp:usedFor |
Data mining
Network monitoring Fault tolerance analysis Finding vulnerabilities in networks Optimizing resource placement |
| gptkbp:usedIn |
gptkb:Bioinformatics
gptkb:Database_Systems Scheduling Network Security Wireless Sensor Networks VLSI Design Resource Allocation Social Network Analysis |
| gptkbp:bfsParent |
gptkb:Reducibility_Among_Combinatorial_Problems_(Karp,_1972)
|
| gptkbp:bfsLayer |
6
|