Re: An algorithm with Minimum vertex cover without considering its performance

eKo1 wrote:
eKo1 wrote:
Perhaps I'm not understanding what a vertex cover is. I thought a
vertex cover was just the set of all vertices which are incident to
edges in E. I guess I'll have to research what a vertex cover is in
more detail.

Let V' be a subset of V. V' is a vertex cover if it satisfies the
following test:

E' = Ø
for each v in V'
for each edge e in E
if v is incident to e then
add e to E'
end if
end for
end for
if |E| = |E'| then
return true // V' is a vertex cover
end if
return false

Would this be correct?

Hi eKo1,
The algorithm you mentioned for a vertex cover is right.

Here is my full new algorithm that can get minimum vertex cover:

To make discussion simpler, we assume that every vertex has a positive
integer, starting with 1 to n and input cells have the following
structure:
(edge count, edge starting vertex, edge ending vertexes).

For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
cell has the following representation: (3, 1, 2, 3, 4). Cell length
vary
dependent on the cell's degree, or the number of edges which is
incident on the cell.

Here is new full algorithm to get minimum vertex cover:
1. Count = 0.
2. If input cell is empty, algorithm ends, otherwise
Sort the input cell serials based on count in increasing order.
3. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;
b. Count++;
c. Print out its edge ending vertex #; (only one)
d. Delete its input cell;
e. In the edge ending vertex cell, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;
b. edge count is decreased by 1;
c. if edge count = 1, set current ending vertex as new
original starting vertex and go to b.
d. if edge count = 0, delete the cell;
4. If input cell is empty, algorithm ends, otherwise
sort the input cell serials based on count in decreasing order.
5. If there is only one cell that has the largest degree, select the
cell
and go to 6. If there are more than one cell that have the equal
largest degree, select the cell that has not been the end vertex
of the last selected cell with the largest degree, or select any of
them
if all of them have have been the end vertexes of last selected cell

with the largest degree.
6. a. Delete its input cell;
b. clear the last setting of LargestDegreeEndVertexFlag,
c. for all edge ending vertex cells, do the followings:
a. delete the original starting vertex in edge ending
vertexes area;
b. edge count is decreased by 1;
c. set new LargestDegreeEndVertexFlag
and go to 2.

Why are there 2-4 procedures:
See examples.
1--2--3--4--5
|
6
|
7
When the algorithm reaches procedure 5, it has output:
2, 4, 6 and Count = 3.

8
|
1--2--3--4--5
|
6
|
7
Output: 2, 4, 6 and 8 and Count = 4.

The reason is, no matter what other parts of graph are,
the vertex outputs must include all its branch end terminal.

Now I give a explanation to the procedure 5-6:
5-6: when there are no claws, delete the cell with largest degree;
but at the same time avoid to use the cells that are the end vertexes
of last select cell with largest degree.

Example for largest cell selection:
(5, 1, 2, 3, 4, 5, 6) (vertex 1 has 5 edges)
(5, 2, 3, 4, 5, 6, 1) (vertex 2 has 5 edges)
(4, 7, 2, 3, 4, 5, 6) (vertex 7 has 4 edges)

step 1: It may select vertex 1 or 2; it selects 1:
(5, 2, 3, 4, 5, 6, 1) --> (4, 2, 3, 4, 5, 6)+
step 2:
(4, 2, 3, 4, 5, 6)+
(4, 7, 2, 3, 4, 5)

'+' indicates it was an ending vertex of last selection vertex with
largest degree.

Both have count = 4, but (4, 2, 3, 4, 5, 6)+ was connected to
the last selection vertex 1, so it should select (4, 7, 2, 3, 4, 5).

This method is used to avoid both vertexes on one edge are selected
to create a situation that would increase chance of duplicate vertex
selection.

Manually I tried more than 20 graphs and get the right answers for
every graph.

Do you have any smart tips?

If you can find a graph that fails the algorithm, please let me know.

Thank you.

Weng

.

Relevant Pages