Brief Announcement: A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs

被引：5

作者：

Alipour, Sharareh ^{[1
]}

Jafari, Amir ^{[2
]}

机构：

[1] Inst Res Fundamental Sci IPM, Sch Comp Sci, Tehran, Iran

[2] Sharif Univ Technol, Dept Math Sci, Tehran, Iran

来源：

PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20) | 2020年

关键词：

Minimum dominating set; Approximation algorithm; Distributed algorithm; planar graph;

D O I：

10.1145/3350755.3400217

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we present a randomized LOCAL constant approximation factor algorithm for minimum dominating set (MDS) problem and minimum total dominating set (MTDS) problem in graphs. The approximation factor of this algorithm for planar graphs with no 4-cycles is 18 and 9 for MDS and MTDS problems, respectively.

引用

页码：501 / 502

页数：2

共 5 条

[1]

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

[2] Brief Announcement: Local Approximability of Minimum Dominating Set on Planar Graphs [J].

Hilke, Miikka ;

Lenzen, Christoph ;

Suomela, Jukka .

PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, :344-346

[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] Survey of Local Algorithms [J].

Suomela, Jukka .

ACM COMPUTING SURVEYS, 2013, 45 (02)

[5]

Wawrzyniak W., 2013, P 2013 ACM S PRINCIP, P406

← 1 →