Finding Good Decompositions for Dynamic Programming on Dense Graphs

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

Mathematics Subject Classification ID

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

• 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