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


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