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.

L is a vertex cover, but not necessarily minimal.

Consider the single edge, two vertex, graph V={1,2}, E={{1,2}},
adjacency matrix:

0 1
1 0

L would be {1,2}, but {1} is also a vertex cover, as is {2}.

Patricia
.

Relevant Pages

  • Re: matrices
    ... d= (ith row of a)*b* ... yes perfectly correct, time being i did the same. ... yes that can be done..but here i need to use for loop! ... The following argument should fit your goal: ...
    (comp.soft-sys.matlab)
  • Re: matrices
    ... d= (ith row of a)*b* ... yes perfectly correct, time being i did the same. ... yes that can be done..but here i need to use for loop! ... How about doing it this way, Priyank? ...
    (comp.soft-sys.matlab)
  • Re: matrices
    ... d= (ith row of a)*b* ... yes perfectly correct, time being i did the same. ... then try to separate your a matrix into ... yes that can be done..but here i need to use for loop! ...
    (comp.soft-sys.matlab)
  • matrices
    ... i have a matrix of size m-by-2 say a and another matrix of ... transpose of a ... what i want to do is (ith row of a)*b* ... how do i do it without using for loop? ...
    (comp.soft-sys.matlab)