direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Gastvorträge 2013

Declarative Problem Solving on Tree Decompositions
Michael Abseher, Bernhard Bliem, TU Vienna
Thursday, November 28, 2013, 4:15 p.m., TU Hochhaus, 5th floor, room 512

Abstract

Many intractable problems become tractable when the treewidth of the instances under consideration is bounded by a constant. One possibility to exploit bounded treewidth is to formulate a dynamic programming algorithm on the instance's tree decompositions. Until now, implementing such algorithms, however, has usually been quite intricate which is due to the lack of supporting tools that offer an adequate language for conveniently specifying such algorithms. We therefore present a method for problem solving that enables the user to specify such algorithms in a declarative way. For this, we employ Answer Set Programming together with a software framework that makes rapid prototyping of algorithms on tree decompositions possible. We illustrate the versatility of the approach by applying it to a selection of different problems. It can be shown that this method is powerful enough to solve all problems parameterized by treewidth in FPT time if they are expressible in monadic second-order logic.

Contact

Vincent Froese, Fachgebiet Algorithmik und Komplexitätstheorie

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Research Colloquium

Algorithmik und Komplexitätstheorie

Webseite