2より小さい近似比率をもつ自己安定的頂点被覆(セッション1)
スポンサーリンク
概要
- 論文の詳細を見る
グラフの頂点被覆とは各辺が少なくとも1つの端点をもつような頂点集合である。最小頂点被覆を決定する問題はNP完全であることがよく知られていて近似アルゴリズムが研究されてきた。自己安定アルゴリズムでは現在までに極大マッチングに基づく2-近似解しか知られていなかった。本稿ではネットワークの最大次数Δに対して(2-1/Δ)-近似比をもつ自己安定アルゴリズムを提案する。まず高次数優先極大マッチングを用いた集中型の(2-1/Δ)-近似アルゴリズムを導入し、同じアイデアに基づいた自己安定アルゴリズムを示す。さらに両者が同じ出力結果となることを証明する。
- 一般社団法人情報処理学会の論文
- 2005-11-11
著者
関連論文
- 2-E-1 A new variant of the minority game-the asset value game
- Lookahead Scheduling Requests for Multi-size Page Caching
- 局所発見不可能な故障のゲーム理論的分析
- 局所発見不可能な故障のゲーム理論的分析
- 1-A-5 Price stabilization and simulation results
- 木型ネットワークにおける単一コータリのニ基準配置問題に関する数値実験
- 木型ネットワークにおける単一コータリーの二基準配置問題に関する数値実験
- Lookahead Scheduling Requests for Efficient Paging (Algorithms and Theory of Computing)
- 動的クラスタリングへ向けて
- 「最適化とその応用」研究部会終了報告(ペーパーフェア)
- 「最適化とその応用」研究部会中間報告(ペーパーフェア)
- 1-E-7 An Efficient and Self-Stabilizing Link Formation Algorithm
- LRU-k法の簡単な近似
- 連鎖的アボートのない多版先読みスケジューラ
- デ-タベ-スシステムにおける動的な版の選択を行うk版先読みスケジュ-ラ
- 動的な版の選択を行う1版先読みスケジュ-ラ
- 2-B-8 On the Price Behavior in a Lazy $-game
- 2-F-2 Self-Stabilizing Message Passing for Mobile Ad hoc Networks(Abstracts,The 2006 Spring National Conference of Operations Research Society of Japan)
- 第54回シンポジウムルポ
- 2-B-11 Towards No Faulty Privileges under Convergence Using Correct Stable Values
- Avoiding almost all faulty privileges in almost linear convergence time (Essays in Commemoration of the Fortieth Anniversary of Department of Management Science)
- A Note on Expected Staying Time Related to Paging
- 二次記憶を用いて収束中の安全性を改善する方法について
- A GAME THEORETIC APPROACH TO PROBE COMPLEXITY IN QUORUM SUSTEMS
- アドホックネットワークに対する自己安定的トークン伝達法
- リクエストに基づいた自己安定的トークン伝達法
- トークン伝達中における仮想リングの反復的構築
- LRUスタックの最適な再構築方策について
- An Extended Depth-first Search : How to Decrease Backtracking (New Developments of Theory of Computation and Algorithms)
- 自己安定深さ優先トークン伝達方式における故障特権の回避について
- 故障度適応封じ込め特性をもつ故障特権の回避
- 全体合理性を満たした自己安定的リンク形成アルゴリズム
- 2より小さい近似比率をもつ自己安定的頂点被覆(セッション1)
- 1-C-9 小売業における新聞売り子問題に関するマルチエージェント・シミュレーション(特別セッション 不確実性環境下での意思決定科学(2))
- 1-G-7 分散システム故障回復への応用を考慮した効率的機雷探索(ゲーム理論(1))