Finding Good Decompositions for Dynamic Programming on Dense Graphs
From MaRDI portal
Publication:2891352
DOI10.1007/978-3-642-28050-4_18zbMath1352.68110MaRDI QIDQ2891352
Jan Arne Telle, Sadia Sharmin, Eivind Magnus Hvidevold, Martin Vatshelle
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_18
90C35: Programming involving graphs or networks
68Q25: Analysis of algorithms and problem complexity
90C59: Approximation methods and heuristics in mathematical programming
90C39: Dynamic programming
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Practical algorithms for MSO model-checking on tree-decomposable graphs, Boolean-width of graphs, A SAT Approach to Clique-Width
Uses Software
Cites Work
- Unnamed Item
- Treewidth computations. II. Lower bounds
- Boolean-width of graphs
- Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition
- Treewidth computations. I: Upper bounds
- A comparison of structural CSP decomposition methods
- On the Boolean-Width of a Graph: Structure and Applications
- A Local Search Algorithm for Branchwidth
- Graph Classes with Structured Neighborhoods and Algorithmic Applications
- Treewidth: Characterizations, Applications, and Computations
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Finding Branch-Decompositions and Rank-Decompositions