### Page Content

### to Navigation

# Secure Sets in Graphs and Declarative Dynamic Programming on Tree Decompositions

**Bernhard Bliem (****TU Wien, Vienna, Austria)**

Abstract: In this talk, I will discuss two self-contained topics: First, I will give an introduction to the Secure Set problem along with some complexity results. A secure set S in a graph is defined as a set of vertices such that for any subset X of S the majority of vertices in the neighborhood of X belongs to S. In the second part of the talk, I will give a brief introduction to Answer Set Programming and show how it can be used for rapid prototyping of dynamic programming (DP) algorithms on tree decompositions (TDs). I will then give an overview of our recent work in this area; in particular I will outline a general procedure that turns any TD-based DP algorithm A that satisfies certain conditions into a TD-based DP algorithm A' such that the following holds when both algorithms are run on the same input: If A and A' produce the sets of solutions S and S', respectively, then S' consists exactly of the subset-minimal elements of S.

Date | Speaker | Location | Language |
---|---|---|---|

08.10.2015 16:15 | Bernhard Bliem | TEL 512 | english |