論文

査読有り 筆頭著者 責任著者
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)
  • Toshihiro Fujito
  • ,
  • Daichi Suzuki

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.

リンク情報
DOI
https://doi.org/10.1007/978-3-319-30139-6_20
DBLP
https://dblp.uni-trier.de/rec/conf/walcom/FujitoS16
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201702221464039679
URL
http://dblp.uni-trier.de/db/conf/walcom/walcom2016.html#conf/walcom/FujitoS16
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

エクスポート
BibTeX RIS