IEICE TRANSACTIONS on Information
OBDD Representation of Intersection Graphs
Summary :
Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.4 pp.824-834
- Publication Date
- 2015/04/01
- Publicized
- 2015/01/16
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2014EDP7281
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Asahi TAKAOKA
Tokyo Institute of Technology
Satoshi TAYU
Tokyo Institute of Technology
Shuichi UENO
Tokyo Institute of Technology
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
Asahi TAKAOKA, Satoshi TAYU, Shuichi UENO, "OBDD Representation of Intersection Graphs" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 4, pp. 824-834, April 2015, doi: 10.1587/transinf.2014EDP7281.
Abstract: Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014EDP7281/_p
Copy
@ARTICLE{e98-d_4_824,
author={Asahi TAKAOKA, Satoshi TAYU, Shuichi UENO, },
journal={IEICE TRANSACTIONS on Information},
title={OBDD Representation of Intersection Graphs},
year={2015},
volume={E98-D},
number={4},
pages={824-834},
abstract={Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.},
keywords={},
doi={10.1587/transinf.2014EDP7281},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - OBDD Representation of Intersection Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 824
EP - 834
AU - Asahi TAKAOKA
AU - Satoshi TAYU
AU - Shuichi UENO
PY - 2015
DO - 10.1587/transinf.2014EDP7281
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2015
AB - Ordered Binary Decision Diagrams (OBDDs for short) are popular dynamic data structures for Boolean functions. In some modern applications, we have to handle such huge graphs that the usual explicit representations by adjacency lists or adjacency matrices are infeasible. To deal with such huge graphs, OBDD-based graph representations and algorithms have been investigated. Although the size of OBDD representations may be large in general, it is known to be small for some special classes of graphs. In this paper, we show upper bounds and lower bounds of the size of OBDDs representing some intersection graphs such as bipartite permutation graphs, biconvex graphs, convex graphs, (2-directional) orthogonal ray graphs, and permutation graphs.
ER -
English
