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

Let A be the adjacency graph of G with the rows and columns ordered 1,
2, ..., n. Let L be an empty list. Do the following:

1. Loop through the A. If you find a 1 at the ith row and jth column,
then add i and j to L.
2. Since L may contain repeated vertices, sort L and loop through it
eliminating repeated vertices.

L now represents the minimum vertex cover of G.


wtxwtx@xxxxxxxxx wrote:
Patricia Shanahan wrote:
wtxwtx@xxxxxxxxx wrote:
Hi,
I know that searching for a minimum vertex cover is a NP-Complete in
computing complexity.

I am interested not in its performance, but in an algorithm that can
get a right solution in theory as a mind exercise.
...

If you really don't care about performance, why not go brute force?

Iterate over the subsets of V, testing each one for being a vertex
cover, and return the smallest subset that passes.

Patricia

Hi Patricia,
As a mind exercise, I prefer to developing a smart algorithm over using
brute force.

I think there are many smart points in this minimum vertex cover design
that have not been used fully.

It may be possible one day the algorithm would be reused as a base in a
polynomial time.

Weng

.

Relevant Pages