Art

J-GLOBAL ID：201502277025428642   Reference number：15A0452213

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

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

Author (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.)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E98.D  Issue： 3  Page： 486-489 (J-STAGE)  Publication year： 2015 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： polyhedron ,  *graph ,  *set ,  *fast algorithm ,  limit ,  aggressive behavior ,  *Computer Security ,  data protection ,  vertex ,  NP complete problem ,  parameter ,  Problem Solving ,  cyberattack
Semi thesaurus term： hypercube ,  security attack ,  fixed-parameter tractability

JST classification (2)： Data protection  (JD01020V) ,  Theory of computation  (JB02000A)

Reference (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.

Terms in the title (5)： グラフ ,  集合 ,  防衛 ,  高速アルゴリズム ,  限界