- This event has passed.
LANS Informal Seminar: Andrew Lyons
January 14, 2009 @ 15:00 CST
Seminar Title: Restricted Coloring on Restricted Classes of Graphs
Speaker: Andrew Lyons, MCS
Date/Time: 2009-01-14 15:00
Location: Building 221 Conference Room A261
Description:
Many problems concerning the optimal evaluation of sparse derivative matrices can be formulated as graph coloring problems. In this talk, we focus on acyclic coloring, which is a restriction on the classic (proper) coloring problem, as well as the further restricted notion of star coloring, both of which arise in the area of sparse Hessian evaluation. In particular, we focus on classes of graphs for which different restricted coloring problems share the same set of solutions. We give characterizations for each of the following classes of graphs.
– The graphs for which every proper coloring is also an acyclic coloring.
– The graphs for which every proper coloring is also a star coloring.
– The graphs for which every acyclic coloring is a star coloring.
These characterizations are useful in that any algorithm for the less restricted coloring problem on these classes may also be used to solve the more restricted version. In some cases, these results directly imply efficient algorithms for finding optimal acyclic and star colorings, while in other cases they allow us to leverage well-established heuristic techniques designed for finding optimal proper colorings. Surprisingly, these results also reveal new connections between some very well-studied classes of graphs. If time permits, we’ll also outline a linear time algorithm for finding optimal acyclic and star colorings on the class of cographs.