Related Problems
- Hitting set is an equivalent reformulation of Set Cover.
- Vertex cover is a special case of Hitting Set.
- Edge cover is a special case of Set Cover.
- Set packing is the dual problem of Set Cover.
- Maximum coverage problem is to choose at most k sets to cover as many elements as possible.
- Dominating set is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown NP complete by reducing Set cover to it.
- Exact cover problem is to choose a set cover with no element included in more than one covering set.
Read more about this topic: Set Cover Problem
Famous quotes containing the words related and/or problems:
“The question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)