- This event has passed.
LANS Informal Seminar: Andrew Lyons
May 20, 2009 @ 15:00 CDT
Seminar Title: Acyclic and Star Colorings of Joins of Graphs and an Algorithm for Cographs
Speaker: Andrew Lyons, Computation Institute
Date/Time: 2009-05-20 15:00
Location: Building 221, room A-261
Description:
We discuss some graphs coloring problems that are related to the efficient evaluation of sparse derivative matrices. In particular, we consider the problems of finding optimal acyclic and star colorings, which model two different methods for the evaluation of Hessians. Both of these problems are known to be intractable even in severely restricted cases. We present a formula that describes the acyclic and star chromatic numbers of graphs that are decomposable with respect to the join operation, which builds a new graph from a collection of two or more disjoint graphs by adding all possible edges between them. We also show that our results lead to linear time algorithms for finding optimal acyclic and star colorings of cographs, which have the unique property that they are recursively decomposable with respect to the join and disjoint union operations.