文献

J-GLOBAL ID：202202247485925650   整理番号：22A0878828

ブロックDAGに対する最大k-独立集合問題の二分決定グラフを用いた解法

Solving the k-independent set problem for BlockDAG using decision diagrams

著者 (2件)： 伝住周平 (東大) ,  川原純 (京大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2022  号： AL-187  ページ： Vol.2022-AL-187,No.2,1-6 (WEB ONLY)  発行年： 2022年03月07日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： DAG型ブロックチェーンにおいて,誠実なブロックを特定する高速なアルゴリズムの設計は重要である.誠実なブロックを特定する問題は,大きなk-独立集合を求める問題として定式化されるが,k-独立集合問題はNP困難であり,高速なアルゴリズム設計が難しい.本研究では,決定グラフを用いて大きなk-独立集合を複数求める高速な手法を提案する.計算機実験によりアルゴリズムの性能を検討する.(著者抄録)

シソーラス用語： *有向グラフ ,  情報技術 ,  *高速アルゴリズム ,  *二分決定グラフ ,  NP困難 ,  計算機シミュレーション ,  解法 ,  ブロックチェーン ,  計算機利用 ,  利用
準シソーラス用語： ZDD ,  計算機実験 ,  非巡回有向グラフ

分類 (1件)： その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (9件)：

• Bryant, R. E.: Graph-based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, Vol. C-35, No. 8, pp. 677-691 (online), DOI: 10.1109/TC.1986.1676819 (1986).
• Iwashita, H. and Minato, S.: Efficient top-down ZDD construction techniques using recursive specifications, TCS Technical Reports, Vol. TCS-TR-A-13-69 (2013).
• Kawahara, J., Inoue, T., Iwashita, H. and Minato, S.: Frontier-based Search for Enumerating All Constrained Subgraphs with Compressed Representation, IEICE Trans. Inf. Syst., Vol. E100-A, No. 9, pp. 1773-1784 (2017).
• Kawahara, J., Saitoh, T., Suzuki, H. and Yoshinaka, R.: Colorful Frontier-based Search: Implicit Enumeration of Chordal and Interval Subgraphs, In Proceedings of the Special Event on Analysis of Experimental Algorithms (SEA² 2019), Vol. 11544, pp. 125-141 (online), DOI: 10.1007/978-3-030-34029-2 9 (2019).
• Knuth, D. E.: The art of computer programming, Vol. 4A, Combinatorial algorithms, Part 1, Addison-Wesley (2011).

タイトルに関連する用語 (5件)： DAG ,  集合 ,  問題 ,  二分決定グラフ ,  解法