On the OBDD size for graphs of bounded tree- and clique-width |
| |
Authors: | Klaus Meer |
| |
Institution: | a Lehrstuhl Theoretische Informatik, Brandenburgische Technische Universität Cottbus, Konrad-Wachsmann-Allee 1, D-03046 Cottbus, Germany b Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany |
| |
Abstract: | We study the size of OBDDs (ordered binary decision diagrams) for representing the adjacency function fG of a graph G on n vertices. Our results are as follows: - -
- for graphs of bounded tree-width there is an OBDD of size O(logn) for fG that uses encodings of size O(logn) for the vertices;
- -
- for graphs of bounded clique-width there is an OBDD of size O(n) for fG that uses encodings of size O(n) for the vertices;
- -
- for graphs of bounded clique-width such that there is a clique-width expression for G whose associated binary tree is of depth O(logn) there is an OBDD of size O(n) for fG that uses encodings of size O(logn) for the vertices;
- -
- for cographs, i.e. graphs of clique-width at most 2, there is an OBDD of size O(n) for fG that uses encodings of size O(logn) for the vertices. This last result complements a recent result by Nunkesser and Woelfel R. Nunkesser, P. Woelfel, Representation of graphs by OBDDs, in: X. Deng, D. Du (Eds.), Proceedings of ISAAC 2005, in: Lecture Notes in Computer Science, vol. 3827, Springer, 2005, pp. 1132-1142] as it reduces the size of the OBDD by an O(logn) factor using encodings whose size is increased by an O(1) factor.
|
| |
Keywords: | Decision diagram Ordered binary decision diagram Tree-width Clique-width Cograph |
本文献已被 ScienceDirect 等数据库收录! |
|