Dominating Sets

Tourist Town #

Like the Graph Coloring problem, the dominating set problem is one that no efficient solution has been found for, even though it is very simple to describe.

This activity explores the problem, and sets it up as the basis for a the Public Key Encryption activity.

Activity description (PDF) #

• Instructions for Dominating sets activity (English)

Translations and other versions #

• Chinese language version
• Polish language Version
• Slovenian language version

Related Resources #

• Wikipedia: Dominating Set
• Wikipedia: Matching (Graph Theory) – In the mathematical discipline of graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. It may also be an entire graph consisting of edges without common vertices.

Curriculum Links #

Great Principles of Computer Science #

• Computation