Practical access to dynamic programming on tree decompositions

DOI10.4230/LIPICS.ESA.2018.6MaRDI QIDQ5009563zbMATH OpenOpenAlexFDO

Authors Max Bannach, Sebastian Berndt

Publication date 4 August 2021

Full work available at URL https://arxiv.org/abs/1806.10176

zbMATH Keywords

fixed-parameter tractabilitymodel-checkingtreewidth

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Practical access to dynamic programming on tree decompositions
• Implementing Courcelle's theorem in a declarative framework for dynamic programming
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• A Practical Approach to Courcelle's Theorem
• Declarative dynamic programming as an alternative realization of Courcelle's theorem

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Courcelle's theorem -- a game-theoretic approach
• Improving the efficiency of dynamic programming on tree decompositions via machine learning
• Jdrasil: a modular library for computing tree decompositions
• Parameterized algorithms
• Parametrized complexity theory.
• Positive-instance driven dynamic programming for treewidth
• SAT-based local improvement for finding tree decompositions of small width
• The complexity of first-order and monadic second-order logic revisited
• The D-FLAT system for dynamic programming on tree decompositions
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration

Cited in

(13)

• Practical access to dynamic programming on tree decompositions
• Positive-instance driven dynamic programming for treewidth
• Declarative dynamic programming as an alternative realization of Courcelle's theorem
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Implementing Courcelle's theorem in a declarative framework for dynamic programming
• Jdrasil: a modular library for computing tree decompositions
• scientific article; zbMATH DE number 1844471 (Why is no real title available?)
• Parameterized leaf power recognition via embedding into graph products
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization
• scientific article; zbMATH DE number 7651198 (Why is no real title available?)
• Parameterized leaf power recognition via embedding into graph products
• Dynamic programming and planarity: improved tree-decomposition based algorithms

Describes a project that uses

Uses Software

• D-FLAT
• Jdrasil
• GitHub

This page was built for publication: Practical access to dynamic programming on tree decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009563)