The dominating set problem is fixed parameter tractable for graphs of bounded genus

被引：17
作者：
Ellis, J
Fan, H
Fellows, M
机构：
[1] Univ Victoria, Dept Comp Sci, Victoria, BC V8W 3P6, Canada
[2] Univ Newcastle, Dept Comp Sci, Newcastle, NSW 2308, Australia
[3] Wilfrid Laurier Univ, Dept Phys & Comp Sci, Waterloo, ON N2L 305, Canada
来源：
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 52卷 / 02期
关键词：
graph; genus; dominating set; fixed parameter algorithm;
D O I：
10.1016/j.jalgor.2004.02.001
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We describe an algorithm for the dominating set problem with time complexity O((4g +40)(k)n(2)) for graphs of bounded genus g greater than or equal to 1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8(k)n(2)) result for planar graphs. Our method is a refinement of the earlier techniques. (C) 2004 Elsevier Inc. All rights reserved.
引用
收藏
页码：152 / 168
页数：17
相关论文
共 15 条
12