The Vertex Cover Problem, Degrees Bounded By 3 (The Vertex Cover Problem)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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

The Vertex Cover Problem - The Vertex Cover Problem, Degrees Bounded By 3 - Time.png