文献

J-GLOBAL ID：202102281593442280   整理番号：21A0220434

多様な部分グラフを発見するアルゴリズム

Algorithms for Finding Diverse Subgraphs

著者 (4件)： HAKANA Tesshu (Chuo Univ.) ,  KOBAYASHI Yasuaki (Kyoto Univ.) ,  KURITA Kazuhiro (National Inst. Informatics) ,  OTACHI Yota (Nagoya Univ.)
資料名： 人工知能学会人工知能基本問題研究会資料  (SIG-FPAI-C)
巻： 113th  ページ： 27-32  発行年： 2020年09月20日 
JST資料番号： X0830A  ISSN： 2436-4584  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： ・現実世界の問題解決では,数学モデルとして問題を定式化し,数学モデルで有効なアルゴリズムを開発して解を得るが,数学モデルから得た解の適用において解の多様性が生ずることが問題であることを指摘。
・Basteらは固定パラメータトラクタビリティの観点から,組合せ問題の多様な解についての計算の研究に着手。
・彼らは多様性測度を最大化する解を発見する問題を考察し,幾つかの周知の問題の多様なバージョンのための固定パラメータトラクタビリティ・アルゴリズムを提示。
・本稿では,多様なスパニング木,パス,部分グラフを発見する問題の固定パラメータトラクタビリティについて考察。
・ペアワイズHamming距離の合計を最大化するグラフのスパニング木を計算する問題が多項式時間で解けることを提示。

シソーラス用語： *部分グラフ ,  *発見的方法 ,  グラフ ,  スパンニング木 ,  *NP完全問題 ,  Hamming距離 ,  多様性 ,  組合せ問題 ,  *発見的アルゴリズム
準シソーラス用語： 連結グラフ ,  *固定パラメータトラクタビリティ ,  *多項式時間アルゴリズム ,  経路計算

分類 (3件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z) ,  計算理論  (JB02000A)

引用文献 (17件)：

• Z. Abbassi, V. S. Mirrokni, and M. Thakur. Diversity maximization under matroid constraints. In Proc. of SIGKDD 2013, p. 32-40, 2013.
• N. Alon, R. Yuster, and U. Zwick. Color-coding. J. ACM, Vol. 42, No. 4, pp. 844-856, 1995.
• J. Baste, M. R. Fellows, L. Jaffke, T. Masarík, M. de Oliveira Oliveira, G. Philip, and F. A. Rosamond. Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. In Proceedings of IJCAI 2020, pp. 1119-1125, 2020.
• J. Baste, L. Jaffke, T. Masarík, G. Philip, and G. Rote. FPT algorithms for diverse collections of hitting sets. Algorithms, Vol. 12, No. 12, p. 254, 2019.
• A. Borodin, A. Jain, H. C. Lee, and Y. Ye. Maxsum diversification, monotone submodular functions, and dynamic updates. ACM Trans. Algorithms, Vol. 13, No. 3, July 2017.

タイトルに関連する用語 (3件)： 部分グラフ ,  発見 ,  アルゴリズム