Art

J-GLOBAL ID：201902230634819407   Reference number：19A0768210

Exact Exponential Algorithm for Distance-3 Independent Set Problem

距離3独立集合問題のための正確な指数アルゴリズム

Author (3)： YAMANAKA Katsuhisa (Faculty of Science and Engineering, Iwate University) ,  KAWARAGI Shogo (Faculty of Science and Engineering, Iwate University) ,  HIRAYAMA Takashi (Faculty of Science and Engineering, Iwate University)
Material： IEICE Transactions on Information and Systems (Web)  (IEICE Trans Inf Syst (Web))
Volume： E102.D  Issue： 3  Page： 499-501(J-STAGE)  Publication year： 2019 
JST Material Number： U0469A  ISSN： 1745-1361  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *set ,  *analysis ,  graph theory ,  subset ,  NP hard
Semi thesaurus term： nondeterministic polynomial-time-hard ,  *algorithm analysis ,  subset ,  *connected dominating set problem ,  simple graph

Author keywords (4)： exact exponential algorithm ,  independent set ,  distance-d independent set ,  maximum distance-d independent set

JST classification (3)： Theory of sets  (AB10000I) ,  Theory of computation  (JB02000A) ,  Basics of graph theory  (IA02020S)

Reference (4)：

• [1] H. Eto, F. Guo, and E. Miyano, “Distance-d independent set problems for bipartite and chordal graphs,” J. Comb. Optim., vol.27, no.1, pp.88-99, 2014. 10.1007/s10878-012-9594-4
• [2] H. Eto, T. Ito, Z. Liu, and E. Miyano, “Approximability of the distance independent set problem on regular graphs and planar graphs,” Proc. 10th International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol.10043, pp.270-284, 2016. 10.1007/978-3-319-48749-6_20
• [3] H. Eto, T. Ito, Z. Liu, and E. Miyano, “Approximation algorithm for the distance-3 independent set problem on cubic graphs,” Proc. 11th International Conference and Workshops on Algorithms and Computation, Lecture Notes in Computer Science, vol.10167, pp.228-240, 2017. 10.1007/978-3-319-53925-6_18
• [4] F.V. Fomin and D. Kratsch, Exact Exponential Algorithms, Texts in Theoretical Computer Science, An EATCS Series, Springer, 2010. 10.1007/978-3-642-16533-7

Terms in the title (4)： 集合 ,  問題 ,  指数 ,  アルゴリズム