Minimum Number of Managers

Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
A group of workers (labeled 1 to
) 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.
Contributed by: Izidor Hafner (March 2013)
Open content licensed under CC BY-NC-SA
Snapshots
Details
In graph theory, this is known as the minimum vertex cover problem.
Reference
[1] S. Permmaraju and S. Skiena, Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, New York: Cambridge University Press, 2003 pp. 317–318.
Permanent Citation
"Minimum Number of Managers"
http://demonstrations.wolfram.com/MinimumNumberOfManagers/
Wolfram Demonstrations Project
Published: March 26 2013