vertex cover

(redirected from Vertex cover problem)
Also found in: Wikipedia.

vertex cover

[′vər‚teks ¦kəv·ər]
(mathematics)
A set of vertices in a graph such that every edge in the graph is incident to at least one vertex in this set.
References in periodicals archive ?
Alimonti and Kann [2] have shown that the Vertex Cover problem restricted to 3-regular connected graphs is APX-complete.
We now give an approximation preserving L-reduction from the Vertex Cover problem in 3-regular connected graphs to MCLP and draw the following conclusions.
The problem is obviously NP-hard on arbitrary graphs since it contains the vertex cover problem as a special case.
4 The Maximum Vertex Cover Problem in Bipartite Graphs
In addition to solving a Sudoku mystery, the team say their work could also be applied to solving the vertex cover problem, which arises in the branch of mathematics known as graph theory and has applications in gene sequencing and software testing.
In a graph G = (V, E), a vertex cover is a subset V[prime] [subset or equal to] V such that, for each edge uv [element of] E, at least one of u and v belongs to V[prime] and the minimum vertex cover problem (VC) is to find a minimum size vertex cover.
A linear-time approximation algorithm for the weighted vertex cover problem.
It was constructed to solve the weighted vertex cover problem in graphs and has a worst-case performance of twice the optimal solution.
Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B.
We now consider the vertex cover problem for the hypergraphs defined in Section 2.
The VERTEX COVER problem seeks the smallest subset S [?
Some subjects examined include vertex cover problems in distributed systems, link prediction in complex networks, computer virus propagation on scale free networks, and social network analysis.