4H-03
恒久的連結頂点被覆問題について
○中村友哉，藤戸敏弘（豊橋技科大）
グラフ上の恒久的頂点被覆問題とは，何名かの守衛をグラフの頂点上に配置し，任意の辺への任意回数の攻撃に対し，守衛がその辺を通過することで，グラフを守り続けるために必要最小な守衛数を求める問題である．
ここでは同問題を拡張し，守衛が連結性をもち，常に連結頂点被覆を構成するような，恒久的連結頂点被覆問題を導入する．
恒久的頂点被覆問題に関する既知結果と同様に，1）グラフが木の場合は線形時間で解け，2）一般グラフではNP困難であるが，2倍近似可能であること，を示す．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会