November 7, 2017 Theory Seminar 4:00 pm, CS 140

Algorithms on Graphs of Bounded Clique Width

David Tench

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.