Inhalt des Dokuments
|Michael Abseher, Bernhard Bliem, TU Vienna |
|Thursday, November 28, 2013, 4:15 p.m., TU Hochhaus, 5th floor, room 512|
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.
ContactVincent Froese, Fachgebiet Algorithmik und Komplexitätstheorie