初等的二部グラフで構成される木における恒久的頂点被覆数について(一般)
スポンサーリンク
概要
- 論文の詳細を見る
頂点上に守衛が配置されたグラフに対し,任意の辺を攻撃する.攻撃された辺の端点に守衛が配置されていれば,その辺を通ってもう一方の端点へ移動することで,守衛はその攻撃からグラフを防御できる.各攻撃に対し,それぞれの守衛は,任意の隣接点へ移動,もしくは現在点にとどまることができる.任意回数の攻撃からグラフを防御し続けることができる守衛の最小数を,そのグラフの恒久的頂点被覆数という.本稿では,木の各辺を任意の初等的二部グラフで置き換えてできるグラフに対し,その恒久的頂点被覆数を導出する.
- 2013-03-11
著者
関連論文
- 多状態スキーレンタル問題に対する最適競合比の解析
- d-claw freeグラフ上の独立集合問題に対する局所探索法について
- 層別グラフにおける有向木被覆問題の近似について (理論計算機科学の深化と応用)
- 最小コスト木状被覆問題の2倍近似アルゴリズム
- 重みつき集合充填問題に対する局所改善法について
- 集合多重被覆問題に対する貪欲法の改良
- 2011年度冬のLAシンポジウム Approximating Steiner Tree and Tree Cover problems in Directed Graphs (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
- 木状泥棒領域を持つグラフ護衛問題の近似
- 木状泥棒領域を持つグラフ護衛問題の近似
- 初等的二部グラフで構成される木における恒久的頂点被覆数について(一般)