Practical access to dynamic programming on tree decompositions

DOI10.3390/A12080172zbMath1461.68091OpenAlexW2967340447WikidataQ127355601 ScholiaQ127355601MaRDI QIDQ2005578

Sebastian Berndt, Max Bannach

Publication date: 8 October 2020

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a12080172

zbMATH Keywords

treewidthmodel checkingfixed-parameter tractability

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

Treewidth-aware reductions of normal \textsc{ASP} to \textsc{SAT} - is normal \textsc{ASP} Harder than \textsc{SAT} after all? ⋮ Exploiting Database Management Systems and Treewidth for Counting ⋮ Solving projected model counting by utilizing treewidth and its limits ⋮ Unnamed Item ⋮ Unnamed Item

Uses Software

• D-FLAT
• Jdrasil

Cites Work

• Unnamed Item
• Courcelle's theorem -- a game-theoretic approach
• SAT-based local improvement for finding tree decompositions of small width
• The complexity of first-order and monadic second-order logic revisited
• Positive-instance driven dynamic programming for treewidth
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Jdrasil: A Modular Library for Computing Tree Decompositions
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

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