WEKO3
アイテム
ブロックDAGに対する最大<i>k</i>-独立集合問題の二分決定グラフを用いた解法
https://ipsj.ixsq.nii.ac.jp/records/217350
https://ipsj.ixsq.nii.ac.jp/records/2173501369034c-ef61-44f4-bb28-ac8f1c126a45
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL22187002.pdf (253.6 kB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-03-07 | |||||||||
| タイトル | ||||||||||
| タイトル | ブロックDAGに対する最大<i>k</i>-独立集合問題の二分決定グラフを用いた解法 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Solving the <i>k</i>-independent set problem for BlockDAG using decision diagrams | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 東京大学 | ||||||||||
| 著者所属 | ||||||||||
| 京都大学 | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| The University of Tokyo | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Kyoto University | ||||||||||
| 著者名 |
伝住, 周平
× 伝住, 周平
× 川原, 純
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | DAG 型ブロックチェーンにおいて，誠実なブロックを特定する高速なアルゴリズムの設計は重要である．誠実なブロックを特定する問題は，大きな k-独立集合を求める問題として定式化されるが，k-独立集合問題は NP 困難であり，高速なアルゴリズム設計が難しい．本研究では，決定グラフを用いて大きな k-独立集合を複数求める高速な手法を提案する．計算機実験によりアルゴリズムの性能を検討する． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2022-AL-187, 号 2, p. 1-6, 発行日 2022-03-07 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
