Implicit Representations of Graphs by OBDDs and Patricia BDDs

スポンサーリンク

概要

• 論文の詳細を見る

• Exploring enormous state graphs represented implicitly by ordered binary decision diagrams (OBDDs) is one of the most successful applications of OBDDs. However, our worst-case analysis of implicit graph representations by OBDDs shows that there are cases where OBDD representations are not optimal and require more space than adjacency lists. As an improvement, we propose a new type of BDDs, called Patricia BDDs, which are capable of implicit representation of graphs while their worst-case sizes are kept equal or less than adjacency lists and OBDDs.

• 社団法人電子情報通信学会の論文
• 1996-07-25

著者

• Iwaihara Mizuho

  Interdisciplinary Graduate School Of Engineering Sciences Kyushu University

• HIROFUJI Masanori

  Interdisciplinary Graduate School of Engineering Sciences, Kyushu University

• Hirofuji Masanori

  Interdisciplinary Graduate School Of Engineering Sciences Kyushu University

関連論文

• Implicit Representations of Graphs by OBDDs and Patricia BDDs

スポンサーリンク