| Item type |
SIG Technical Reports(1) |
| 公開日 |
2022-01-20 |
| タイトル |
|
|
タイトル |
有界モデル検査による独立集合遷移問題の解法に関する考察 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
On Solving Independent Set Reconfiguration Problems with Bounded Model Checking |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
電気通信大学大学院情報理工学研究科 |
| 著者所属 |
|
|
|
東北大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
京都大学大学院情報学研究科 |
| 著者所属 |
|
|
|
神戸大学情報基盤センター |
| 著者所属 |
|
|
|
東北大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
兵庫県立大学大学院情報科学研究科 |
| 著者名 |
戸田, 貴久
伊藤, 健洋
川原, 純
宋, 剛秀
鈴木, 顕
照山, 順一
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
独立集合遷移問題とは，グラフの独立集合に所定の変更操作を繰り返し適用して，初期の独立集合から目標の独立集合へと遷移させることができるかどうか判定する問題である．これは，もっともよく研究されている組合せ遷移問題の一つである．本研究では，変更操作の適用回数が限定された場合において，この問題に対する有界モデル検査を用いた解法を考察する． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
The INDEPENDENT SET RECONFIGURATION problem, which is one of the most well-studied reconfiguration problems, is to determine whether two given independent sets of a graph can be transformed into each other by repeatedly applying a prescribed operation. In this study, we consider the case where the number of applications of the operation is bounded, and propose methods to solve the case with bounded model checking. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2022-AL-186,
号 5,
p. 1-7,
発行日 2022-01-20
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL22186005.pdf (885.9 kB)
