Finding Good Decompositions for Dynamic Programming on Dense Graphs
DOI10.1007/978-3-642-28050-4_18zbMath1352.68110OpenAlexW96963885MaRDI 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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (4)
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
This page was built for publication: Finding Good Decompositions for Dynamic Programming on Dense Graphs