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


eKo1 wrote:
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

Hi eKo1,
Thank you very much.

1. I don't know what the adjacency graph of G. Please tell it in more
details.

2. The following operations can be simplified by setting 1 to i's or
j's bit of a bit array L; If K's bit of the bit array L = 1, the vertex
K is selected.

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

3. Please let me know where the algorithm come from. If there is a
reference, please let me know.

I would like to study your algorithm very carefully.

To find a 1 at the ith row and jth column is a n^2 operation.
As we believe minimum vertex cover is a NP-Complete problem. Your
algorithm to find adjacency graph of G seems to be a NP-Complete
problem too.

It is not essential to me that the deriving adjancency graph of a graph
is a NP-Complete problem, but it is important for me on how it is
derived and it must be a minimum vertex cover.

Thank you again.

Weng

.

Relevant Pages

  • An algorithm with Minimum vertex cover without considering its performance
    ... I am interested not in its performance, but in an algorithm that can ... Given a graph G =, how to find a minimum vertex cover for the ... (edge count, edge starting vertex, edge ending vertexs). ... Sort the input cell serials based on count in increasing order. ...
    (comp.theory)
  • Re: Minimum vertex cover algorithm in theory
    ... I am interested not in its performance, but in an algorithm that can ... Given a graph G =, how to find a minimum vertex cover for the ... Edge ending point count is decreased by 1; ...
    (comp.programming)
  • Re: Minimum vertex cover algorithm in theory
    ... propaul wrote: ... I am interested not in its performance, but in an algorithm that can ... Given a graph G =, how to find a minimum vertex cover for the ...
    (comp.programming)
  • Minimum vertex cover algorithm in theory
    ... I am interested not in its performance, but in an algorithm that can ... Given a graph G =, how to find a minimum vertex cover for the ... Edge ending point count is decreased by 1; ...
    (comp.programming)