二分決定図
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/07/09 06:02 UTC 版)
二分決定図（にぶんけっていず、英: Binary Decision Diagram, BDD）や二分決定グラフ（にぶんけっていグラフ）とは、ブール関数を表現するのに使われる有向非巡回グラフである。グラフに既約していない物は二分決定木（binary decision tree）と呼ぶ。
- ^ C. Y. Lee. "Representation of Switching Circuits by Binary-Decision Programs". Bell Systems Technical Journal, 38:985–999, 1959.
- ^ Sheldon B. Akers. "Binary Decision Diagrams". IEEE Transactions on Computers, C-27(6):509–516, June 1978.
- ^ Raymond T. Boute, "The Binary Decision Machine as a programmable controller". EUROMICRO Newsletter, Vol. 1(2):16-22, January 1976.
- ^ Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation". IEEE Transactions on Computers, C-35(8):677–691, 1986.
- ^ R. E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293-318.
- ^ Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "Efficient Implementation of a BDD Package". In Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC 1990), pages 40–45. IEEE Computer Society Press, 1990.
- ^ Beate Bollig, Ingo Wegener. "Improving the Variable Ordering of OBDDs Is NP-Complete". IEEE Transactions on Computers, 45(9):993––1002, September 1996.
- ^ Detlef Sieling. "The nonapproximability of OBDD minimization." Information and Computation 172, 103-138. 2002.
- ^ Rice, Michael. “A Survey of Static Variable Ordering Heuristics for Efficient BDD/MDD Construction”. 2016年2月28日閲覧。
[続きの解説]
「二分決定図」の続きの解説一覧
- 1 二分決定図とは
- 2 二分決定図の概要
- 3 変数の順序付け
- 4 実装
- 二分決定図のページへのリンク
