Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141803 | Discrete Optimization | 2006 | 10 Pages |
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%.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Nadja Betzler, Rolf Niedermeier, Johannes Uhlmann,