文献

J-GLOBAL ID：202202260852816736   整理番号：22A0420294

有界モデル検査による独立集合遷移問題の解法に関する考察

On Solving Independent Set Reconfiguration Problems with Bounded Model Checking

著者 (6件)： 戸田貴久 (電通大 大学院情報理工学研究科) ,  伊藤健洋 (東北大 大学院情報科学研究科) ,  川原純 (京大 大学院情報学研究科) ,  宋剛秀 (神戸大 情報基盤セ) ,  鈴木顕 (東北大 大学院情報科学研究科) ,  照山順一 (兵庫県大 大学院情報科学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2022  号： AL-186  ページ： Vol.2022-AL-186,No.5,1-7 (WEB ONLY)  発行年： 2022年01月20日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 独立集合遷移問題とは,グラフの独立集合に所定の変更操作を繰り返し適用して,初期の独立集合から目標の独立集合へと遷移させることができるかどうか判定する問題である.これは,もっともよく研究されている組合せ遷移問題の一つである.本研究では,変更操作の適用回数が限定された場合において,この問題に対する有界モデル検査を用いた解法を考察する.(著者抄録)

シソーラス用語： *モデル検査 ,  限界 ,  *状態 ,  独立性 ,  *集合 ,  変化 ,  解法 ,  モデル ,  実験 ,  無向グラフ
準シソーラス用語： 有界 ,  遷移 ,  変更 ,  行列モデル ,  評価実験

分類 (1件)： その他の情報工学基礎理論  (JB06000C)

引用文献 (13件)：

• Ito, T., Demaine, E. D., Harvey, N. J., Papadimitriou, C. H., Sideri, M., Uehara, R. and Uno, Y.: On the complexity of reconfiguration problems, Theoretical Computer Science, Vol. 412, No. 12, pp. 1054-1065 (online),DOI: 10.1016/j.tcs.2010.12.005 (2011).
• Nishimura, N.: Introduction to Reconfiguration, Algorithms, Vol. 11, No. 4 (online), DOI: 10.3390/a11040052(2018).
• 東北大学,明電舎共同プレスリリース: 配電損失の最適化と切替手順の同時算出が可能に-電力の発送電分離を目前に自動計算の手法開発,2019年6月27日配信.
• Kamiński, M., Medvedev, P. and Milanič, M.: Complexity of independent set reconfigurability problems, Theoretical Computer Science, Vol. 439, pp. 9-15 (online),DOI: 10.1016/j.tcs.2012.03.004 (2012).
• Mouawad, A. E., Nishimura, N., Raman, V., Simjour, N. and Suzuki, A.: On the Parameterized Complexity of Reconfiguration Problems, Algorithmica, Vol. 78, No. 1, pp. 274-297 (online), DOI: 10.1007/s00453-016-0159-2(2017).

タイトルに関連する用語 (6件)： 有界 ,  モデル検査 ,  集合 ,  遷移 ,  問題 ,  解法