New upper bounds on the decomposability of planar graphs and fixed parameter algorithms
New upper bounds on the decomposability of planar graphs and fixed parameter algorithms
复制标题
平面图可分解性和固定参数算法的新上限
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Thilikos
中科院分区：
文献类型：
--
作者：
F. Fomin;D. Thilikos
众所周知，有n个顶点的平面图的分枝宽度/树宽有界于alphasqrt{n}。在……里面
在许多算法应用程序中，拥有一个
常数α上的小界。我们给出了一个证明
到目前为止，最好的上界是常数α。
特别是，对于树宽的情况，α<；3.182
对于分支宽度的情况，α<；2.122。我们的证据
是基于Alon的平面分离定理，
Seymour&Thomas与图的某些极大极小定理
未成年人系列。基于这些界限，我们引入了一个新的
一种解决不同固定参数问题的方法
平面图。我们证明我们的方法提供了最好的
到目前为止，基本问题的指数加速
平面图的顶点覆盖、支配集、独立集
还有其他许多人。
It is known that a planar graph on n vertices has branch-width/tree-width bounded by alphasqrt{n}. In
many algorithmic applications it is useful to have a
small bound on the constant alpha. We give a proof of
the best, so far, upper bound for the constant alpha.
In particular, for the case of tree-width, alpha<3.182
and for the case of branch-width, alpha<2.122. Our proof
is based on the planar separation theorem of Alon,
Seymour & Thomas and some min-max theorem of the graph
minors series. Based on these bounds we introduce a new
method for solving different fixed parameter problems on
planar graphs. We prove that our method provides the best
so far exponential speed-up for fundamental problems on
planar graphs like Vertex Cover, Dominating Set, Independent Set
and many others.