Minimum Number of Managers

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.