Set Cover Problem - Related Problems

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:

    “In the middle years of childhood, it is more important to keep alive and glowing the interest in finding out and to support this interest with skills and techniques related to the process of finding out than to specify any particular piece of subject matter as inviolate.”
    —Dorothy H. Cohen (20th century)

    “I am always glad to think that my education was, for the most part, informal, and had not the slightest reference to a future business career. It left me free and untrammeled to approach my business problems without the limiting influence of specific training.”
    —Alice Foote MacDougall (1867–1945)