Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs
Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs
复制标题
平面图和地图中 (k, r) 中心的固定参数算法
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
D. Thilikos
中科院分区：
文献类型：
--
作者：
E. Demaine;F. Fomin;M. Hajiaghayi;D. Thilikos
<i>(<i>k</i>, <i>r</i>)中心问题</i>询问输入图<i>G</i>是否具有≤<i>k</i>个顶点（称为<i>中心</i>），使得<i>G</i>的每个顶点与某个中心的距离≤<i>r</i>。在本文中，我们证明了（<i>k</i>, <i>r</i>）中心问题，参数化为<i>k</i>和<i>r</i>)在平面图上是定参数可处理的（FPT），即它承认复杂度<i>f</i>(<i>k</i>, <i>r</i>)<i>n</i><sup><i>O</i>(1)</sup>，其中函数<i>f</i>与<i>n</i>无关。特别是,我们表明,f <我> < / i >(<我> k, r < / i >) = 2 <一口> < i > O < / i >(<我> < / i >日志<我> r < / i >) &ksqrt;</sup>，其中指数项的指数在中心数量上呈次线性增长。此外，我们证明了对于Chen、Grigni和Papadimitriou引入的更一般的<i>映射图</i>类，可以设计相同类型的FPT算法。我们的结果结合了小分支宽度图的动态规划算法和图论结果，该结果将该参数限定为<i>k</i>和<i>r</i>。最后，我们的算法的一个副产品是在平面图和映射图中<i>r</i>-控制问题的PTAS的存在。我们的方法建立在Robertson和Seymour关于Graph minor的开创性结果的基础上，因此比Alber等人之前的机器在平面图上的指数加速要强大得多。为了展示我们的结果的通用性，我们展示了如何将我们的算法扩展到网格上“大”的一般参数。此外，我们使用分支宽度而不是通常的树宽度使我们能够获得更快的算法，并且需要比标准的叶/引入/忘记/连接结构更复杂的动态规划。我们的结果也是独一无二的，因为它们适用于非次闭的图类，即平面图和地图图的常幂。
The <i>(<i>k</i>, <i>r</i>)-center problem</i> asks whether an input graph <i>G</i> has ≤<i>k</i> vertices (called <i>centers</i>) such that every vertex of <i>G</i> is within distance ≤<i>r</i> from some center. In this article, we prove that the (<i>k</i>, <i>r</i>)-center problem, parameterized by <i>k</i> and <i>R</i>, is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity <i>f</i>(<i>k</i>, <i>r</i>)<i>n</i><sup><i>O</i>(1)</sup> where the function <i>f</i> is independent of <i>n</i>. In particular, we show that <i>f</i>(<i>k,r</i>) = 2<sup><i>O</i>(<i>r</i> log <i>r</i>) &ksqrt;</sup>, where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of <i>map graphs</i> introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of <i>k</i> and <i>r</i>. Finally, a byproduct of our algorithm is the existence of a PTAS for the <i>r</i>-domination problem in both planar graphs and map graphs.Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are “large” on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.