Tree Decompositions of Graphs: Saving Memory in Dynamic Programming

DOI10.1016/J.ENDM.2004.03.023MaRDI QIDQ3439128zbMATH OpenOpenAlexFDO

Authors Nadja Betzler, Rolf Niedermeier, Johannes Uhlmann

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2004.03.023

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Tree decompositions of graphs: saving memory in dynamic programming
• Efficient problem solving on tree decompositions using binary decision diagrams
• Improving the efficiency of dynamic programming on tree decompositions via machine learning
• Space saving by dynamic algebraization based on tree-depth
• scientific article; zbMATH DE number 2149351

Cites work

• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• Memory requirements for table computations in partial k-tree algorithms
• Tree Decompositions with Small Cost

Cited in

(11)

• Memory requirements for table computations in partial k-tree algorithms
• Space saving by dynamic algebraization based on tree-depth
• Tree decompositions of graphs: saving memory in dynamic programming
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Improving the efficiency of dynamic programming on tree decompositions via machine learning
• Efficient problem solving on tree decompositions using binary decision diagrams
• scientific article; zbMATH DE number 2149351 (Why is no real title available?)
• Memory requirements for table computations in partial k-tree algorithms
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• Exact algorithms and applications for tree-like Weighted Set Cover
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies

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 Q3439128)