vertex cover


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 ?
It is clear that [absolute value of V] = [absolute value of S] and V is a vertex cover of G; that is, any edge of G is incident to at least one node in V.
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.
In this paper, we prove, by reduction from vertex cover in 3-regular connected graphs, that MCLP is APX-hard for graphs that are monochromatic-diamond-free.
Recall that a vertex cover is a set of vertices that cover every edge of the graph.
First we show that the problem is APX-hard by a reduction from Vertex Cover that provides a stronger factor than other hardness proofs in the context of barrier resilience.
Our proof shows in particular that the maximum vertex cover problem--also known as the partial vertex cover problem--is NP-hard on bipartite graphs.
A subset C of V(G) is said a minimal vertex cover for G if every edge of G is incident with one vertex in C and there is no proper subset of C having such a property.
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.
This algorithm needs temporary array that is assigned to each thread independently called vertex cover of size (C).
Let S = {[v.sub.1], [v.sub.2], ..., [v[alpha].sub.0]} be a minimum vertex cover of G.
Other topics examined include approximate majority and probabilistic time, the complexity of polynomials and their coefficient functions, a linear round lower bound for Lovasz- Schrijver SDP relaxations of vertex cover, and directed planar reachability in unambiguous log-space.
Finding a maximum independent set is equivalent to finding a maximum clique or a minimum vertex cover of a graph, and all three problems are NP-hard [Garey and Johnson 1979].