2016年3月
Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- ,
- 巻
- 9627
- 号
- 開始ページ
- 251
- 終了ページ
- 262
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-319-30139-6_20
- 出版者・発行元
- Springer Verlag
A local algorithm is a deterministic (i.e., non-randomized) distributed algorithm in an anonymous port-numbered network running in a constant number of synchronous rounds, and this work studies the approximation performance of such algorithms. The problems treated are b-edge dominating set (b-EDS) that is a multiple domination version of the edge dominating set (EDS) problem, and t-total vertex cover (t- TVC) that is a variant of the vertex cover problem with a clustering property. After observing that EDS and 2-TVC are approximable within 4 and 3, respectively, using a single run of the local algorithm for finding a maximal matching in a bicolored graph, it will be seen that running the maximal matching local algorithm for bicolored graph twice, 2-EDS and 3-TVC can be approximated within factors 2 and 3, respectively.
- リンク情報
- ID情報
-
- DOI : 10.1007/978-3-319-30139-6_20
- ISSN : 1611-3349
- ISSN : 0302-9743
- DBLP ID : conf/walcom/FujitoS16
- J-Global ID : 201702221464039679
- SCOPUS ID : 84961142043