The Vertex Cover Problem, Degrees Bounded By 3

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.

Parameters

$n$ : number of vertices
$m$ : number of edges
$k$ : size of vertex cover

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

				See more
J. Chen; L. Liu; and W. Jia.	2000	$O(k 1.2192^k)$	$O(k^3)$ auxiliary (potentially $O(k^2)$ )

Reductions Table

Insuffient Data to display table

Other relevant algorithms