The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus

The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus
复制标题

有界亏格图的支配集问题是固定参数可处理的

DOI：
--
复制
发表时间：
2002
期刊：
Scandinavian Workshop on Algorithm Theory
影响因子：
--
通讯作者：
M. Fellows
M. Fellows
中科院分区：
--
文献类型：
--
作者：
J. Ellis;Hongbing Fan;M. Fellows

文献摘要

被引文献

相似文献

我们描述了一种针对有界属 g 的图的支配集问题的时间复杂度为 O((24g2 + 24g + 1)kn2) 的算法，其中 k 是集合的大小。先前已经表明，这个问题对于平面图来说是可处理的固定参数。我们的方法是对早期技术的改进。
We describe an algorithm for the dominating set problem withtime complexity O((24g2 + 24g + 1)kn2) for graphs of bounded genus g, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. Our method is a refinement of the earlier techniques.