direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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.

Zusatzinformationen / Extras