IEICE TRANSACTIONS on Fundamentals
Implicit Representations of Graphs by OBDDs and Patricia BDDs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.7 pp.1068-1078
- Publication Date
- 1996/07/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- VLSI Design Technology and CAD
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Mizuho IWAIHARA, Masanori HIROFUJI, "Implicit Representations of Graphs by OBDDs and Patricia BDDs" in IEICE TRANSACTIONS on Fundamentals,
vol. E79-A, no. 7, pp. 1068-1078, July 1996, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_7_1068/_p
Copy
@ARTICLE{e79-a_7_1068,
author={Mizuho IWAIHARA, Masanori HIROFUJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Implicit Representations of Graphs by OBDDs and Patricia BDDs},
year={1996},
volume={E79-A},
number={7},
pages={1068-1078},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Implicit Representations of Graphs by OBDDs and Patricia BDDs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1068
EP - 1078
AU - Mizuho IWAIHARA
AU - Masanori HIROFUJI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 1996
AB - 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.
ER -
English
