Skip to main content

Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

Problems 5, 6, & 14: Node Cover, Set Cover, and Exact Cover

A topic by procmeal games created Sep 06, 2022 Views: 60
Viewing posts 1 to 1
HostSubmitted (1 edit)

In node cover (also known as vertex cover), the input is a graph G.  The goal is to find a set of vertices such that every edge touches one of the vertices in the set.

Here's a video about it: https://youtu.be/1KkT7y8nxH0

In set cover, the input is a set U and subsets S1, S2, ..., Sm.  The unions of the subsets must be U.  The goal is to find the smallest collection of subsets such that they include all the elements of U.

Here's a video about it: https://youtu.be/XmW3xR-0CSE .  This video includes an explanation of how set cover and node cover are basically the same.

Exact cover is a lot like set cover.  It has the set U and subsets S1, S2, ..., Sm.  However, the collection of subsets chosen must not contain any of the same elements.  Each subset in the exact cover must be disjoint from every other subset in the cover.  The exact cover does not need to be the smallest collection like in set cover.

This video is relevant to exact cover: https://youtu.be/_cR9zDlvP88