Notices
Results 1 to 3 of 3

Thread: Vertex Cover definition

  1. #1 Vertex Cover definition 
    Forum Freshman
    Join Date
    Feb 2009
    Posts
    7
    Would this be considered a correct definition of the vertex cover problem?

    "Set of minimum number of vertices of an undirected graph such that any edge of the graph is incident on at least one vertex in the set "

    RK


    Reply With Quote  
     

  2.  
     

  3. #2  
    WYSIWYG Moderator marnixR's Avatar
    Join Date
    Apr 2007
    Location
    Cardiff, Wales
    Posts
    5,810
    you mean like this ?


    "Reality is that which, when you stop believing in it, doesn't go away." (Philip K. Dick)
    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Feb 2009
    Posts
    7
    Wikipedia defines Vertex Cover to be

    http://en.wikipedia.org/wiki/Vertex_cover_problem

    a vertex cover of a graph is a set of vertices such that each edge of the graph touches (is incident with) at least one element of the set.

    What if i change the definition to

    a vertex cover of a graph is a set of vertices such that ANY edge of the graph touches (is incident with) at least one element of the set.

    Does changing the definition from each to ANY make a difference? Is there a catch somewhere. I saw problem definition with the word ANY and i am wondering if it still the Vertex Cover problem definition and hence NP-Complete?

    RK
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •