(thing) by flyingroc Fri Nov 10 2000 at 19:36:07
A vertex cover is a set of vertices in a graph such that every edge in the graph is incident (connected) to at least one vertex in the set. The set of all vertices, for example, is a vertex cover

The vertex cover problem is: given a graph and an integer k, is there a vertex cover for the graph with <= k vertices?

It has been proven that the vertex cover problem is NP-complete. However, it is possible to answer the vertex cover problem for bipartite graphs in polynomial time.

del.icio.us Facebook Digg StumbleUpon Reddit (I like it!)
Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.