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

Patricia Shanahan wrote:
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}.

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.

Sorry...

.

Relevant Pages

  • Re: Modeling General Graphs in SQL
    ... > I am trying to come up with a way to model a general graph in SQL ... the one edge paths are: ... > These rows can be generated from the single edge paths using a CTE ... node_id int, ...
    (comp.databases)
  • General Graphs in SQL
    ... I am trying to come up with a way to model a general graph in SQL which ... Now we can add the two edge paths: ... These rows can be generated from the single edge paths using a CTE ... The first observations are that if we have a cycle of size in ...
    (comp.databases.theory)
  • Modeling General Graphs in SQL
    ... I am trying to come up with a way to model a general graph in SQL which ... Now we can add the two edge paths: ... These rows can be generated from the single edge paths using a CTE ... The first observations are that if we have a cycle of size in ...
    (comp.databases)