The Vertex Cover Problem, Degrees Bounded By 3: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:The Vertex Cover Problem, Degrees Bounded By 3 (The Vertex Cover Problem)}} == Description == A vertex cover of a graph $G$ is a set $C$ of vertices such that every edge of $G$ has at least one endpoint in $C$. The vertex cover problem is to find a minimum-size vertex cover in a given graph $G$. This version of the problem is such that the input graph $G$ has all vertices' degree bounded by 3. == Related Problems == Generalizations: The Vertex Cover...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
$n$: number of vertices | |||
$m$: number of edges | |||
$k$: size of vertex cover | |||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 23: | Line 27: | ||
|- | |- | ||
|} | |} | ||
== Time Complexity Graph == | |||
[[File:The Vertex Cover Problem - The Vertex Cover Problem, Degrees Bounded By 3 - Time.png|1000px]] | |||
Latest revision as of 10:09, 28 April 2023
Description
A vertex cover of a graph $G$ is a set $C$ of vertices such that every edge of $G$ has at least one endpoint in $C$. The vertex cover problem is to find a minimum-size vertex cover in a given graph $G$. This version of the problem is such that the input graph $G$ has all vertices' degree bounded by 3.
Related Problems
Generalizations: The Vertex Cover Problem
Parameters
$n$: number of vertices
$m$: number of edges
$k$: size of vertex cover
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| J. Chen; L. Liu; and W. Jia. | 2000 | $O(k*{1.2192}^k)$ | $O(k^{3})$ auxiliary? (potentially $O(k^{2})$??) | Exact | Deterministic | Time |
Time Complexity Graph
