Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs

被引：13

作者：

Hilke, Miikka ^{[1
]}

Lenzen, Christoph ^{[2
]}

Suomela, Jukka ^{[3
]}

机构：

[1] Univ Helsinki, Helsinki Inst Informat Technol HIIT, Dept Comp Sci, Helsinki, Finland

[2] MIT, Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA

[3] Aalto Univ, Helsinki Inst Informat Technol HIIT, Dept Informat & Comp Sci, Espoo, Finland

来源：

PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14) | 2014年

基金：

芬兰科学院;

关键词：

Approximation algorithm; dominating set problem; local distributed algorithm; lower bound; planar graph; APPROXIMATIONS;

D O I：

10.1145/2611462.2611504

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a (7 - epsilon)-approximation of a minimum dominating set on planar graphs, for any positive constant epsilon. In prior work, the best lower bound on the approximation ratio has been 5 - epsilon; there is also an upper bound of 52.

引用

页码：344 / 346

页数：3

共 8 条

[1]

Czygrinow A, 2008, LECT NOTES COMPUT SC, V5218, P78, DOI 10.1007/978-3-540-87779-0_6

[2] Lower Bounds for Local Approximation [J].

Goeoes, Mika ;

Hirvonen, Juho ;

Suomela, Jukka .

JOURNAL OF THE ACM, 2013, 60 (05)

[3] Distributed minimum dominating set approximations in restricted families of graphs [J].

Lenzen, Christoph ;

Pignolet, Yvonne-Anne ;

Wattenhofer, Roger .

DISTRIBUTED COMPUTING, 2013, 26 (02) :119-137

[4]

Lenzen Christoph, 2011, THESIS

[5] On a problem of formal logic [J].

Ramsey, FP .

PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1930, 30 :264-286

[6] Survey of Local Algorithms [J].

Suomela, Jukka .

ACM COMPUTING SURVEYS, 2013, 45 (02)

[7] A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs [J].

Wawrzyniak, Wojciech .

INFORMATION PROCESSING LETTERS, 2014, 114 (03) :94-98

[8]

Wawrzyniak Wojciech, 2013, PODC 2013, P406, DOI 10.1145/2484239.2484281

← 1 →