2026-04-20T19:51:58Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00217350 2025-01-19T15:31:51Z 1164:2592:10824:10900

ブロックDAGに対する最大<i>k</i>-独立集合問題の二分決定グラフを用いた解法 Solving the <i>k</i>-independent set problem for BlockDAG using decision diagrams 伝住, 周平 川原, 純 DAG 型ブロックチェーンにおいて，誠実なブロックを特定する高速なアルゴリズムの設計は重要である．誠実なブロックを特定する問題は，大きな k-独立集合を求める問題として定式化されるが，k-独立集合問題は NP 困難であり，高速なアルゴリズム設計が難しい．本研究では，決定グラフを用いて大きな k-独立集合を複数求める高速な手法を提案する．計算機実験によりアルゴリズムの性能を検討する． technical report 情報処理学会 2022-03-07 application/pdf 研究報告アルゴリズム（AL） 2 2022-AL-187 1 6 2188-8566 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/217350/files/IPSJ-AL22187002.pdf jpn