Space Saving by Dynamic Algebraization Based on Tree-Depth
Space Saving by Dynamic Algebraization Based on Tree-Depth
复制标题
基于树深度的动态代数节省空间
DOI：
--
复制
发表时间：
2017
影响因子：
0.5
通讯作者：
Huiwen Yu
中科院分区：
文献类型：
--
作者：
Martin Fürer;Huiwen Yu
动态规划广泛用于基于图的树分解的精确计算。然而，空间复杂度通常是指数的树宽。研究了基于多项式空间树分解的动态规划算法的设计问题。我们展示了如何使用树分解和扩展代数技术的Lokshtanov和Nederlof（在：第42届ACM研讨会上的理论计算，pp. 321-330，2010），使得典型的动态编程算法在时间O t（2 h）内运行，其中h是树深度（Nešetziil等人，EUR. 27（6）：1022-1041，2006）。一般来说，我们假设给出了深度为h的树分解。我们将我们的算法计算完美匹配的网格上的问题，并表明它优于其他多项式空间的解决方案。我们也将该算法应用于其他集合覆盖和划分问题。
Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based on tree decompositions in polynomial space. We show how to use a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof (In: 42nd ACM Symposium on Theory of Computing, pp. 321–330, 2010) such that a typical dynamic programming algorithm runs in time O∗(2h), where h is the tree-depth (Nešetřil et al., Eur. J. Comb. 27(6):1022–1041, 2006) of a graph. In general, we assume that a tree decomposition of depth h is given. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.
DOI：
10.1007/978-3-642-04128-0_51
发表时间：
2009-09
期刊：
--
影响因子：
--
作者：
Johan M. M. van Rooij-Johan-M.-M.-van-Rooij-1796712;H. Bodlaender;P. Rossmanith
通讯作者：
Johan M. M. van Rooij-Johan-M.-M.-van-Rooij-1796712;H. Bodlaender;P. Rossmanith