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

Mathematics Subject Classification ID

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)

A SAT Approach to Clique-Width ⋮ 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

Uses Software

• DIMACS
• Treewidthlib
• ComputeTW

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