文献

J-GLOBAL ID：201502277025428642   整理番号：15A0452213

グラフのセキュア集合と防衛同盟:高速アルゴリズムと改良された限界

Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds

著者 (4件)： AMANO Kazuyuki (Depertment of Computer Sci., Gunma Univ.) ,  OO Kyaw May (Univ. of Computer Studies, Yangon) ,  OTACHI Yota (School of Information Sci., Japan Advanced Inst. of Sci. and Technol.) ,  UEHARA Ryuhei (School of Information Sci., Japan Advanced Inst. of Sci. and Technol.)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E98.D  号： 3  ページ： 486-489 (J-STAGE)  発行年： 2015年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： グラフのセキュア集合と防衛同盟について研究した。それらは幾つかの意味において安全な頂点の集合である。本論文では,実行時間が以前の既知アルゴリズムよりもずっと高速な,小さなセキュア集合を発見するための固定パラメータアルゴリズムを提示した。その上で,超立方体における防衛同盟とセキュア集合の最小サイズに対する改良された限界を提示した。これらの成果は近年休止した幾つかの未解決問題を解決する。(翻訳著者抄録)

シソーラス用語： 多面体 ,  *グラフ ,  *集合 ,  *高速アルゴリズム ,  限界 ,  攻撃行動 ,  *コンピュータセキュリティ ,  データ保護 ,  頂点 ,  NP完全問題 ,  パラメータ ,  問題解決 ,  サイバー攻撃
準シソーラス用語： 超立方体 ,  セキュリティ攻撃 ,  固定パラメータトラクタビリティ

分類 (2件)： データ保護  (JD01020V) ,  計算理論  (JB02000A)

引用文献 (17件)：

• [1] R.C. Brigham, R.D. Dutton, and S.T. Hedetniemi, “Security in graphs,” Discrete Appl. Math., vol.155, pp.1708-1714, 2007.
• [2] F.R.K. Chung, Z. Füredi, R.L. Graham, and P.D. Seymour, “On induced subgraphs of the cube,” J. Comb. Theory, Ser. A, vol.49, pp.180-187, 1988.
• [3] R.D. Dutton, “The evolution of a hard graph theory problem - secure sets,” A course material of COT 6410: Computational Complexity, University of Central Florida, 2010. Available at http://www.cs.ucf.edu/courses/cot6410/spr2010/doc/SecureSets.doc
• [4] R.D. Dutton, “On a graph's security number,” Discrete Math., vol.309, pp.4443-4447, 2009.
• [5] R.D. Dutton, R. Lee, and R.C. Brigham, “Bounds on a graph's security number,” Discrete Appl. Math., vol.156, pp.695-704, 2008.

タイトルに関連する用語 (5件)： グラフ ,  集合 ,  防衛 ,  高速アルゴリズム ,  限界