Tree decompositions of graphs: saving memory in dynamic programming

DOI10.1016/J.DISOPT.2006.05.008MaRDI QIDQ2465936zbMATH OpenOpenAlexFDO

Authors Nadja Betzler, Johannes Uhlmann, Rolf Niedermeier

Publication date 11 January 2008

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.05.008

zbMATH Keywords

(nice) tree decompositions of graphsdynamic programminggraph algorithmsmemory usageset covering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Recommendations

• Tree Decompositions of Graphs: Saving Memory in Dynamic Programming
• Improving the efficiency of dynamic programming on tree decompositions via machine learning
• Efficient problem solving on tree decompositions using binary decision diagrams
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Space saving by dynamic algebraization based on tree-depth

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• Algorithms – ESA 2004
• Bidimensionality: new connections between FPT algorithms and PTASs
• Exact algorithms and applications for tree-like Weighted Set Cover
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• Experiments on data reduction for optimal domination in networks
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 2086260 (Why is no real title available?)
• scientific article; zbMATH DE number 1979494 (Why is no real title available?)
• scientific article; zbMATH DE number 2079336 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• Memory requirements for table computations in partial k-tree algorithms
• Optimal Capacity Scheduling—I
• Practical algorithms on partial k-trees with an application to domination-like problems
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• SOFSEM 2005: Theory and Practice of Computer Science
• Solving frequency assignment problems via tree-decomposition
• Solving partial constraint satisfaction problems with tree decomposition
• Tree decompositions with small cost
• Treewidth. Computations and approximations
• Treewidth: computational experiments

Cited in

(14)

• Memory requirements for table computations in partial k-tree algorithms
• Space saving by dynamic algebraization based on tree-depth
• Graph minors and parameterized algorithm design
• Improving the efficiency of dynamic programming on tree decompositions via machine learning
• Tree Decompositions of Graphs: Saving Memory in Dynamic Programming
• Efficient problem solving on tree decompositions using binary decision diagrams
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Confronting intractability via parameters
• scientific article; zbMATH DE number 2149351 (Why is no real title available?)
• Space saving by dynamic algebraization
• Memory requirements for table computations in partial k-tree algorithms
• Path cover problems with length cost
• Parameterized algorithms for computing Pareto sets
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

Describes a project that uses

Uses Software

• LEDA
• BRITE

This page was built for publication: Tree decompositions of graphs: saving memory in dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2465936)