2013 | OriginalPaper | Buchkapitel
Declarative Dynamic Programming as an Alternative Realization of Courcelle’s Theorem
verfasst von : Bernhard Bliem, Reinhard Pichler, Stefan Woltran
Erschienen in: Parameterized and Exact Computation
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Many computationally hard problems become tractable if the graph structure underlying the problem instance exhibits small treewidth. A recent approach to put this idea into practice is based on a declarative interface to specify dynamic programming over tree decompositions, delegating the computation to dedicated solvers. In this paper, we prove that this method can be applied to any problem whose fixed-parameter tractability follows from Courcelle’s Theorem.