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 ?
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.
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).
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].
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.
It was constructed to solve the weighted vertex cover problem in graphs and has a worst-case performance of twice the optimal solution.
Potentially, many graph invariants, such as the domination number and the vertex cover number, can be studied in their tropical version.