|
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 NP-complete graph problems have polynomial time algorithms on bounded-clique-width graphs. In this talk we explore some of these results and demonstrate applications to current work on practically-motivated graph problems.