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:
“One does not realize the historical sensation as a re-experiencing, but as an understanding that is closely related to the understanding of music, or rather of the world by means of music.”
—Johan Huizinga (1872–1945)
“We are all adult learners. Most of us have learned a good deal more out of school than in it. We have learned from our families, our work, our friends. We have learned from problems resolved and tasks achieved but also from mistakes confronted and illusions unmasked. . . . Some of what we have learned is trivial: some has changed our lives forever.”
—Laurent A. Daloz (20th century)