WOLFRAM|DEMONSTRATIONS PROJECT

Minimum Number of Managers

​
number of people
7
new problem
special case
choose managers
1
2
3
4
5
6
7
A group of
n
workers (labeled 1 to
n
) interact in pairs, as shown by a line between them. Any worker can be a manager, and for each red line, at least one must be a manager. The task is to find a minimum number of managers. Try this heuristic: at each stage, choose a person with a maximal number of links. The special case is provided to show that this heuristic does not always work.