TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 08.10.2015


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.

Bernhard Bliem
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe