Page Content
Feedback vertex set on graphs of low clique-width
Ondra Suchy (Universität des Saarlandes)
This talk is especially suitable for those not familiar with
clique-width and willing to understand what is it all about. We use a
non-standard dynamic programming on a so-called k-module decomposition
of a graph to solve the Feedback Vertex Set problem, which asks whether
a graph contains q vertices meeting all its cycles. This is not a local
property, in the sense that we cannot check if q vertices meet all
cycles by looking only at their neighbors. Dynamic programming
algorithms for problems based on non-local properties are usually more
complicated. Here, given a graph G of clique-width cw and a
cw-expression of G, we solve the Minimum Feedback Vertex Set problem in
time O(n^2 * 2^{O(cw log cw)}).
This is a joint work with B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle.
date | speaker | location | language |
---|---|---|---|
24.01.2012 14:00 | Ondra Suchy | FR 6510 | english |