文献

J-GLOBAL ID：202102223318385817   整理番号：21A0967717

順列グラフのカラフル独立集合問題に対するアルゴリズム

著者 (3件)： 吉村仁志 (京大) ,  小林靖明 (京大) ,  山本章博 (京大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2021  号： AL-182  ページ： Vol.2021-AL-182,No.3,1-6 (WEB ONLY)  発行年： 2021年03月10日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフのカラフル独立集合問題は,頂点に色がついたグラフが与えられ,頂点集合の部分集合で独立かつカラフル,つまり部分集合内の任意の頂点が互いに隣接せずかつ色が相異なるもので最大の要素数のものを見つける問題である.この問題は,通常の最大独立集合問題の一般化であり,与えられたグラフが特定のグラフクラスに属する場合でも興味深い分析が行われている.本研究では,与えられたグラフが順列グラフの場合を考え,この問題の固定パラメータアルゴリズムや指数時間厳密アルゴリズムを議論する.(著者抄録)

シソーラス用語： *グラフ理論 ,  部分集合 ,  グラフ ,  決定問題 ,  アルゴリズム ,  NP困難 ,  計算量理論 ,  多項式 ,  マトロイド ,  定理証明
準シソーラス用語： *カラフル独立集合問題 ,  *順列グラフ ,  判定問題 ,  パラメータアルゴリズム ,  指数時間厳密アルゴリズム

分類 (1件)： 計算理論  (JB02000A)

引用文献 (18件)：

• Yuichi Asahiro, Jesper Jansson, Guohui Lin, Eiji Miyano, Hirotaka Ono, and Tadatoshi Utashima. Exact algorithms for the repetition-bounded longest common subsequence problem. Theor. Comput. Sci., Vol. 838, pp. 238-249, 2020.
• Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, and Irina Shapira. Scheduling split intervals. SIAM J. Comput., Vol. 36, No. 1, pp. 1-15, 2006.
• Arindam Biswas, Venkatesh Raman, and Saket Saurabh. Solving group interval scheduling efficiently. In Charles J. Colbourn, Roberto Grossi, and Nadia Pisanti, editors, Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23-25, 2019, Proceedings, Vol. 11638 of Lecture Notes in Computer Science, pp. 97-107. Springer, 2019.
• Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, and Florian Sikora. On the parameterized complexity of the repetition free longest common subsequence problem. Inf. Process. Lett., Vol. 112, No. 7, pp. 272-276, 2012.
• Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., Vol. 75, No. 8, pp. 423-434, 2009.

タイトルに関連する用語 (4件)： 順列 ,  グラフ ,  集合 ,  アルゴリズム