文献

J-GLOBAL ID：201902230634819407   整理番号：19A0768210

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

Exact Exponential Algorithm for Distance-3 Independent Set Problem

著者 (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)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E102.D  号： 3  ページ： 499-501(J-STAGE)  発行年： 2019年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： G=(V,E)を重みなしの単純グラフとした。距離d独立セットは,Iの任意の2つの頂点u,vについて,dist(u,v)≧dとなるようなサブセットI⊆Vであり,ここで,dist(u,v)は,uとvの間の距離である。次に,最大距離d独立集合問題では,頂点の最大数で距離d独立集合のサイズを計算する必要がある。固定整数d≧3でも,この問題はNP困難である。本論文は,O(1.4143ⁿ)時間で最大距離3独立セットのサイズを計算する正確な指数アルゴリズムを設計した。(翻訳著者抄録)

シソーラス用語： *集合 ,  *解析 ,  グラフ理論 ,  部分集合 ,  NP困難 ,  *アルゴリズム解析 ,  *結合支配集合
準シソーラス用語： NP困難問題 ,  サブセット ,  *結合支配集合問題 ,  単純グラフ

著者キーワード (4件)： 正確な指数アルゴリズム ,  独立集合 ,  距離-D独立集合 ,  最大距離-D独立集合

分類 (3件)： 集合論  (AB10000I) ,  計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (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

タイトルに関連する用語 (4件)： 集合 ,  問題 ,  指数 ,  アルゴリズム