کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141803 | 957092 | 2006 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Tree decompositions of graphs: Saving memory in dynamic programming
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Tree decompositions of graphs: Saving memory in dynamic programming Tree decompositions of graphs: Saving memory in dynamic programming](/preview/png/1141803.png)
چکیده انگلیسی
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%.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 3, Issue 3, 1 September 2006, Pages 220–229
Journal: Discrete Optimization - Volume 3, Issue 3, 1 September 2006, Pages 220–229
نویسندگان
Nadja Betzler, Rolf Niedermeier, Johannes Uhlmann,