2024-03-29T13:43:59Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001806182023-11-17T02:17:36Z06504:09168:09184
恒久的連結頂点被覆問題についてjpnソフトウェア科学・工学http://id.nii.ac.jp/1001/00180530/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=180618&item_no=1&attribute_id=1&file_no=1Copyright (c) 2017 by the Information Processing Society of Japan豊橋技科大豊橋技科大中村, 友哉藤戸, 敏弘グラフ上の恒久的頂点被覆問題とは,何名かの守衛をグラフの頂点上に配置し,任意の辺への任意回数の攻撃に対し,守衛がその辺を通過することで,グラフを守り続けるために必要最小な守衛数を求める問題である.ここでは同問題を拡張し,守衛が連結性をもち,常に連結頂点被覆を構成するような,恒久的連結頂点被覆問題を導入する.恒久的頂点被覆問題に関する既知結果と同様に,1)グラフが木の場合は線形時間で解け,2)一般グラフではNP困難であるが,2倍近似可能であること,を示す.AN00349328第79回全国大会講演論文集201712472482017-03-162017-05-22