Tree decompositions of graphs: Saving memory in dynamic programming

Tree decompositions of graphs: Saving memory in dynamic programming

0.00 Avg rating0 Votes
Article ID: iaor2007904
Country: Netherlands
Volume: 3
Issue: 3
Start Page Number: 220
End Page Number: 229
Publication Date: Sep 2006
Journal: Discrete Optimization
Authors: , ,
Keywords: programming: dynamic, sets
Abstract:

We propose a simple and effective heuristic to save memory in dynamic programming on tree decompositions when solving graph optimization problems. The introduced ‘anchor technique’ is based on a tree-like set covering problem. We substantiate our findings by experimental results. Our strategy has negligible computational overhead concerning running time but achieves memory savings for nice tree decompositions and path decompositions between 60% and 98%.

Reviews

Required fields are marked *. Your email address will not be published.