cfry@watdcsu.waterloo.edu (C.Fry - Inst. Computer Research) (01/15/88)
Quick Solutions to Optimization Problems
on Perfect Graphs
by
Prof. Bruce Reed
of
Department of Combinatorics and Optimization
University of Waterloo
Abstract
Two famous hard optimization problems are colouring the vertices
of a graph and finding the largest clique in a graph. These
problems are known to be NP-complete for general graphs. In
1960, Claude Berge defined the class of perfect graphs. Both the
colouring and clique problems can be solved in polynomial time on
these graphs. We discuss algorithms to solve these problems on
some special classes of perfect graphs. We discuss applications
of these algorithms in scheduling, micro-code generation and com-
putational geometry.
DATE: Wednesday January 20, 1988
TIME: 3:30 p.m.
PLACE: MC 5158
Everyone is welcome. Refreshments served.