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)

Abstract

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.