Abstract
A graph G = (V,E) can be described by the characteristic function of the edge set \(\mathcal{X}_E\) which maps a pair of binary encoded nodes to 1 iff the nodes are adjacent. Using Ordered Binary Decision Diagrams (OBDDs) to store \(\mathcal{X}_E\) can lead to a (hopefully) compact representation. Given the OBDD as an input, symbolic/implicit OBDD-based graph algorithms can solve optimization problems by mainly using functional operations, e.g., quantification or binary synthesis. While the OBDD representation size can not be small in general, it can be provable small for special graph classes and then also lead to fast algorithms. In this paper, we show that the OBDD size of unit interval graphs is O( ∣ V ∣ /log ∣ V ∣ ) and the OBDD size of interval graphs is O( ∣ V ∣ log ∣ V ∣ ) which both improve a known result from Nunkesser and Woelfel (2009). Furthermore, we can show that using our variable order and node labeling for interval graphs the worst-case OBDD size is Ω( ∣ V ∣ log ∣ V ∣ ). We use the structure of the adjacency matrices to prove these bounds. This method may be of independent interest and can be applied to other graph classes. We also develop a maximum matching algorithm on unit interval graphs using O(log ∣ V ∣ ) operations and evaluate the algorithm empirically.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Arnold, D.B., Sleep, M.R.: Uniform random generation of balanced parenthesis strings. ACM Trans. Program. Lang. Syst. 2(1), 122–128 (1980)
Bloem, R., Gabow, H.N., Somenzi, F.: An algorithm for strongly connected component analysis in n log n symbolic steps. Formal Methods in System Design 28(1), 37–56 (2006)
Bollig, B.: On symbolic OBDD-based algorithms for the minimum spanning tree problem. TCS 447, 2–12 (2012)
Bollig, B., Gillé, M., Pröger, T.: Implicit computation of maximum bipartite matchings by sublinear functional operations. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol. 7287, pp. 473–486. Springer, Heidelberg (2012)
Bollig, B., Löbbing, M., Wegener, I.: On the effect of local changes in the variable ordering of ordered decision diagrams. IPL 59(5), 233–239 (1996)
Bollig, B., Pröger, T.: An efficient implicit OBDD-based algorithm for maximal matchings. In: Dediu, A.-H., Martín-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 143–154. Springer, Heidelberg (2012)
Bollig, B., Wegener, I.: Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems. Journal of Computer and System Sciences 61(3), 558–579 (2000)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers 35(8), 677–691 (1986)
Burch, J.R., Clarke, E.M., McMillan, K.L., Dill, D.L., Hwang, L.J.: Symbolic model checking: 1020 states and beyond. Information and Computation 98(2), 142–170 (1992)
Chung, Y., Park, K., Cho, Y.: Parallel maximum matching algorithms in interval graphs. In: Proc. of the 4th ICPADS, pp. 602–609 (1997)
Coudert, O.: Doing two-level logic minimization 100 times faster. In: Proc. of the 6th SODA, pp. 112–121 (1995)
Gentilini, R., Piazza, C., Policriti, A.: Computing strongly connected components in a linear number of symbolic steps. In: Proc. of the 14th SODA, pp. 573–582 (2003)
Gentilini, R., Piazza, C., Policriti, A.: Symbolic graphs: Linear solutions to connectivity related problems. Algorithmica 50(1), 120–158 (2008)
Gillé, M.: OBDD-Based Representation of Interval Graphs. ArXiv e-prints (2013), http://arxiv.org/abs/1305.2772
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, vol. 57. North-Holland Publishing Co. (2004)
Hachtel, G.D., Somenzi, F.: A symbolic algorithms for maximum flow in 0-1 networks. Formal Methods in System Design 10(2/3), 207–219 (1997)
Hosaka, K., Takenaga, Y., Kaneda, T., Yajima, S.: Size of ordered binary decision diagrams representing threshold functions. Theor. Comput. Sci. 180(1-2), 47–60 (1997)
Lai, Y.-T., Pedram, M., Vrudhula, S.B.K.: EVBDD-based algorithms for integer linear programming, spectral transformation, and function decomposition. IEEE Transactions on CAD of Integrated Circuits and Systems 13(8), 959–975 (1994)
Meer, K., Rautenbach, D.: On the OBDD size for graphs of bounded tree- and clique-width. Discrete Mathematics 309(4), 843–851 (2009)
Meinel, C., Theobald, T.: On the influence of the state encoding on OBDD-representations of finite state machines. ITA 33(1), 21–32 (1999)
Mertzios, G.B.: A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters 21(4), 332–337 (2008)
Nunkesser, R., Woelfel, P.: Representation of graphs by OBDDs. Discrete Applied Mathematics 157(2), 247–261 (2009)
Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory, pp. 139–146 (1969)
Saitoh, T., Yamanaka, K., Kiyomi, M., Uehara, R.: Random generation and enumeration of proper interval graphs. IEICE Transactions 93-D(7), 1816–1823 (2010)
Sawitzki, D.: Implicit flow maximization by iterative squaring. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2004. LNCS, vol. 2932, pp. 301–313. Springer, Heidelberg (2004)
Sawitzki, D.: The complexity of problems on implicitly represented inputs. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 471–482. Springer, Heidelberg (2006)
Sawitzki, D.: Exponential lower bounds on the space complexity of OBDD-based graph algorithms. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 781–792. Springer, Heidelberg (2006)
Sieling, D., Wegener, I.: NC-algorithms for operations on binary decision diagrams. Parallel Processing Letters 3, 3–12 (1993)
Wegener, I.: Branching programs and binary decision diagrams. SIAM Monographs on Discrete Mathematics and Applications (2000)
Woelfel, P.: Symbolic topological sorting with OBDDs. Journal of Discrete Algorithms 4, 51–71 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gillé, M. (2013). OBDD-Based Representation of Interval Graphs. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds) Graph-Theoretic Concepts in Computer Science. WG 2013. Lecture Notes in Computer Science, vol 8165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45043-3_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-45043-3_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45042-6
Online ISBN: 978-3-642-45043-3
eBook Packages: Computer ScienceComputer Science (R0)