UAH > Math > Colloquia > 10/19/2007
For the class of colored problems under consideration, the vertices /nodes of a graph are partitioned into color classes. Each node can represent a person, an object to be stored, or a job to be completed. Problems considered include forming committees or job scheduling under various constraints. Typical problems have constraints that involve people/jobs that can not serve together or be scheduled simultaneously. Further constraints might involve people/jobs that must be placed/executed together. Edges of the graph represent the conflicts, and the color classes indicate the simultaneity constraints.
A mixture of mathematics, operations research and computer science will be presented. In particular, it will be shown that the colored-independence and colored-domination problems are NP-complete even when the graphs considered are restricted to be simply (as simple as possible a case as) the paths, and even when rather severe restrictions are placed on the possible color classes.