2024-03-29T07:14:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001578922023-04-27T10:00:04Z01164:02592:08452:08603
Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex CoversFast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Coversenghttp://id.nii.ac.jp/1001/00157858/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=157892&item_no=1&attribute_id=1&file_no=1Copyright (c) 2016 by the Information Processing Society of JapanDepartment of Computer Science and Engineering, Toyohashi University of TechnologyDepartment of Computer Science and Engineering, Toyohashi University of TechnologyToshihiro, FujitoDaichi, SuzukiA 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.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.AN1009593X研究報告アルゴリズム(AL)2016-AL-1577162016-02-282188-85662016-02-25