WEKO3
アイテム
恒久的連結頂点被覆問題について
https://ipsj.ixsq.nii.ac.jp/records/180618
https://ipsj.ixsq.nii.ac.jp/records/18061812b66e1f-48d1-4048-8fb4-8e12efb4b01b
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2017 by the Information Processing Society of Japan
|
Item type | National Convention(1) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
公開日 | 2017-03-16 | |||||||||
タイトル | ||||||||||
タイトル | 恒久的連結頂点被覆問題について | |||||||||
言語 | ||||||||||
言語 | jpn | |||||||||
キーワード | ||||||||||
主題Scheme | Other | |||||||||
主題 | ソフトウェア科学・工学 | |||||||||
資源タイプ | ||||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_5794 | |||||||||
資源タイプ | conference paper | |||||||||
著者所属 | ||||||||||
豊橋技科大 | ||||||||||
著者所属 | ||||||||||
豊橋技科大 | ||||||||||
著者名 |
中村, 友哉
× 中村, 友哉
× 藤戸, 敏弘
|
|||||||||
論文抄録 | ||||||||||
内容記述タイプ | Other | |||||||||
内容記述 | グラフ上の恒久的頂点被覆問題とは,何名かの守衛をグラフの頂点上に配置し,任意の辺への任意回数の攻撃に対し,守衛がその辺を通過することで,グラフを守り続けるために必要最小な守衛数を求める問題である.ここでは同問題を拡張し,守衛が連結性をもち,常に連結頂点被覆を構成するような,恒久的連結頂点被覆問題を導入する.恒久的頂点被覆問題に関する既知結果と同様に,1)グラフが木の場合は線形時間で解け,2)一般グラフではNP困難であるが,2倍近似可能であること,を示す. | |||||||||
書誌レコードID | ||||||||||
収録物識別子タイプ | NCID | |||||||||
収録物識別子 | AN00349328 | |||||||||
書誌情報 |
第79回全国大会講演論文集 巻 2017, 号 1, p. 247-248, 発行日 2017-03-16 |
|||||||||
出版者 | ||||||||||
言語 | ja | |||||||||
出版者 | 情報処理学会 |