Competitive Otimization Parameters for Graphs
Colloquium in Honor of Mathematics Awareness Month
Dr. Peter Slater
Department of Mathematical Sciences
University of Alabama in Huntsville
April 30, 2004
202 Madison Hall
3:00 PM (Coffee and cookies at 2:30)
Problems such as finding a maximum independent set in a graph have applications in problems such as chemical storage and examination scheduling. Because of the inherent difficulty of the discrete versions of such optimization problems, various forms of games have been developed so as to aid in understanding the nature of these problems (and to simply have some fun).
Competitive optimization parameters in graphs are those associated with the formation of a set S of elements of a graph G, where the set S is formed by two players alternately selecting elements of S. The players are trying to maximize, respectively, minimize, the order of S. Cases to be considered include those where S must be independent, enclaveless, a packing or an acquisition set.
- Hits: 89