2より小さい近似比率をもつ自己安定的頂点被覆

• Item type: SIG Technical Reports(1)
• 公開日: 2005-11-11
• タイトル: 2より小さい近似比率をもつ自己安定的頂点被覆
• タイトル / 言語: en
• タイトル: Approximation of Self-Stabilizing Vertex Cover Less than 2
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 兵庫県立大学経済学部応用経済学科
• 著者所属(英): en
• 著者所属(英): Department of Applied Economics, University of Hyogo
• 著者名: 木庭, 淳
• 著者名(英): Jun, Kiniwa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフの頂点被覆とは各辺が少なくとも1つの端点をもつような頂点集合である。最小頂点被覆を決定する問題はNP完全であることがよく知られていて近似アルゴリズムが研究されてきた。自己安定アルゴリズムでは現在までに極大マッチングに基づく2-近似解しか知られていなかった。本稿ではネットワークの最大次数△に対して（2－1／△）-近似比をもつ自己安定アルゴリズムを提案する。まず高次数優先極大マッチングを用いた集中型の（2－1／△）-近似アルゴリズムを導入し、同じアイデアに基づいた自己安定アルゴリズムを示す。さらに両者が同じ出力結果となることを証明する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A vertex cover of a graph is a subset of vertices such that ea.ch edge has at least one endpoint in the subset. Determining the l71inimum vertex cover is a. well-known _TIP-complete problem in a sequential setting. Thus only a 2-approximation solution based on a self-stabilizing maximal 1natChing has been obviously known until now_ In this paper we propose a new self-stabili21ing vertex cover algorithm that achieves (2 - 1/A)-approximation ratio, where A is the maximum degree of a. given network. We first introduce a sequential (2- 1/A)- approximation algorithm that uses a. maximal matching with the high-degree-first order of vertices. Then we present a self-stabilizing algorithm based oil the same idea, and show that the output of the algorithm is the same as that of the sequential one.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2005, 号 110(2005-AL-103), p. 25-32, 発行日 2005-11-11
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会