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

被引：0

作者：

Ellis, J ^{[1
]}

Fan, H

Fellows, M

机构：

[1] Univ Victoria, Victoria, BC V8W 3P6, Canada

[2] Univ Newcastle, Newcastle, NSW 2308, Australia

来源：

ALGORITHM THEORY - SWAT 2002 | 2002年 / 2368卷

关键词：

graph; genus; dominating set; fixed parameter algorithm;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We describe an algorithm for the dominating set problem with time complexity O((24g(2) + 24g + 1)(k) n(2)) 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.

引用

页码：180 / 189

页数：10

共 10 条

[1]

Alber J, 2001, LECT NOTES COMPUT SC, V2136, P111

[2]

Alber J, 2001, LECT NOTES COMPUT SC, V2076, P261

[3]

Alber J, 2000, LECT NOTES COMPUT SC, V1851, P97

[4]

ALBER J, 2001, WSI20018 U TUB

[5]

ALBER J, 2002, LNCS

[6]

[Anonymous], PARAMETERIZED COMPLE

[7]

[Anonymous], FEASIBLE MATH

[8]

Bollobas B., 1986, COMBINATORICS

[9] THE JORDAN-SCHONFLIES THEOREM AND THE CLASSIFICATION OF SURFACES [J].

THOMASSEN, C .

AMERICAN MATHEMATICAL MONTHLY, 1992, 99 (02) :116-130

[10]

THOMASSEN C, 1995, HDB COMBINATORICS, V1

← 1 →