minimum vertex cover

minimum vertex cover

[‚min·ə·məm ′vər‚teks ‚kəv·ər]
(mathematics)
A vertex cover in a graph such that there is no other vertex cover with fewer vertices.
References in periodicals archive ?
* VERTEX COVER: find a minimum vertex cover (of the edges) of a graph G with c vertices and m edges;
Fortunately, a maximal match can be constructed by a simple greedy algorithm and its vertices are a vertex cover with cardinality C [less than or equal to] 2*(VC) where VC is the cardinality of a minimum vertex cover [19].
Let [V*.sub.c] be a minimum vertex cover of G, and let P* be a minimum monochromatic clique partition of H.
On the other hand, we can obtain a monochromatic clique partition P of H from a minimum vertex cover [V*.sub.c] of G, as follows.
We show this by an approximation factor preserving reduction from MINIMUM VERTEX COVER.
Let S = {[v.sub.1], [v.sub.2], ..., [v[alpha].sub.0]} be a minimum vertex cover of G.
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].
Given a graph G, let us consider a minimum vertex cover [C.sup.*] ([absolute value of [C.sup.*]] = [Tau](G)) and the corresponding maximum independent set [S.sup.*].
Consequently, computing the minimum connected tropical subgraph in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] determines the minimum Vertex Cover of G.
Note that Lemma 2 does not imply that finding a minimum vertex cover is in P if a minimum twin-cover is provided--in fact, a minimum vertex cover may not intersect with a minimum twin-cover at all (e.g., in a complete graph with one missing edge).
Note that Lemma 2 does not imply that finding a minimum vertex cover is in P if a minimum twin-cover is pro[v.sub.i]ded - in fact, a minimum vertex cover may not intersect with a minimum twin-cover at all (e.g., in a complete graph with one missing edge).
Note that the maximum independent set and minimum vertex cover problems are complementary.
Full browser ?