
Algorithms on Graphs of Bounded Clique Width
David Tench
UMass
Abstract: The clique width of a graph is a parameter that in some sense expresses its structural complexity. Graphs of bounded clique width have strong structure which can be exploited algorithmically, most notably in that many NPcomplete graph problems have polynomial time algorithms on boundedcliquewidth graphs. In this talk we explore some of these results and demonstrate applications to current work on practicallymotivated graph problems.