Questions tagged [vertex-cover]
The vertex-cover tag has no usage guidance.
0
votes
0answers
9 views
Bi-criteria combinatorial approximation algorithms for min k-vertex cover
Min k-vertex cover: Given a graph $G = (V,E)$, the goal of the min k-vertex cover problem is to output $k$ vertices from $V$ such that the number of uncovered edges in $E$ is minimized.
It is easy to ...
0
votes
1answer
24 views
set cover to edge cover
I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I ...
1
vote
1answer
39 views
Partitioning vertices in a bipartite graph according to minimum vertex covers
How to solve this problem?
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover ...