91
个编辑
更改
跳到导航
跳到搜索
第114行：
第114行： +
无编辑摘要
同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt|Kneis|Mölle|Richter|Rossmanith|2005}}; {{harvtxt|Björklund|Husfeldt|2008}}.</ref>
同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt|Kneis|Mölle|Richter|Rossmanith|2005}}; {{harvtxt|Björklund|Husfeldt|2008}}.</ref>
==注释==
==注释==