Abstract
Graphs can be represented symbolically by the Ordered Binary Decision Diagram (OBDD) of their characteristic function. To solve problems in such implicitly given graphs, specialized symbolic algorithms are needed which are restricted to the use of functional operations offered by the OBDD data structure. In this paper, a symbolic algorithm for the all-pairs shortest-paths (APSP) problem in loopless directed graphs with strictly positive integral edge weights is presented. It requires \(\Theta\bigl(\log^{2}(NB)\bigr)\) OBDD-operations to obtain the lengths and edges of all shortest paths in graphs with N nodes and maximum edge weight B. It is proved that runtime and space usage are polylogarithmic w. r. t. N and B on graph sequences with characteristic bounded-width functions. This convenient property is closed under certain graph composition operations. Moreover, an alternative symbolic approach for general integral edge weights is sketched which does not behave efficiently on general graph sequences with bounded-width functions. Finally, two variants of the APSP problem are briefly discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bahar, R.I., Frohm, E.A., Gaona, C.M., Hachtel, G.D., Macii, E., Pardo, A., Somenzi, F.: Algebraic decision diagrams and their applications. In: ICCAD 1993, pp. 188–191. IEEE Press, Los Alamitos (1993)
Bloem, R., Gabow, H.N., Somenzi, F.: An algorithm for strongly connected component analysis in n log n symbolic steps. In: Johnson, S.D., Hunt Jr., W.A. (eds.) FMCAD 2000. LNCS, vol. 1954, pp. 37–54. Springer, Heidelberg (2000)
Bryant, R.E.: Symbolic manipulation of Boolean functions using a graphical representation. In: DAC 1985, pp. 688–694. ACM Press, New York (1985)
Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers 35, 677–691 (1986)
Cohen, E., Zwick, U.: All-pairs small-stretch paths. Journal of Algorithms 38, 335–353 (2001)
Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM Journal on Computing 29, 1740–1759 (2000)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.: Complexity of problems on graphs represented as OBDDs. Chicago Journal of Theoretical Computer Science 1999 (1999)
Gentilini, R., Piazza, C., Policriti, A.: Computing strongly connected components in a linear number of symbolic steps. In: SODA 2003, pp. 573–582. ACM Press, New York (2003)
Gentilini, R., Policriti, A.: Biconnectivity on symbolically represented graphs: A linear solution. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 554–564. Springer, Heidelberg (2003)
Hachtel, G.D., Hermida, M., Pardo, A., Poncino, M., Somenzi, F.: Re-Encoding sequential circuits to reduce power dissipation. In: ICCAD 1994, pp. 70–73. IEEE Press, Los Alamitos (1994)
Hachtel, G.D., Somenzi, F.: Logic Synthesis and Verification Algorithms. Kluwer Academic Publishers, Boston (1996)
Hachtel, G.D., Somenzi, F.: A symbolic algorithm for maximum flow in 0–1 networks. Formal Methods in System Design 10, 207–219 (1997)
Hojati, R., Touati, H., Kurshan, R.P., Brayton, R.K.: Efficient ω-regular language containment. In: Probst, D.K., von Bochmann, G. (eds.) CAV 1992. LNCS, vol. 663, pp. 396–409. Springer, Heidelberg (1993)
Jin, H., Kuehlmann, A., Somenzi, F.: Fine-grain conjunction scheduling for symbolic reachability analysis. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol. 2280, p. 312–326. Springer, Heidelberg (2002)
Krause, M.: BDD-based cryptanalysis of keystream generators. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 222–237. Springer, Heidelberg (2002)
Moon, I., Kukula, J.H., Ravi, K., Somenzi, F.: To split or to conjoin: The question in image computation. In: DAC 2000, pp. 23–28. ACM Press, New York (2000)
Ravi, K., Bloem, R., Somenzi, F.: A comparative study of symbolic algorithms for the computation of fair cycles. In: Johnson, S.D., Hunt Jr., W.A. (eds.) FMCAD 2000. LNCS, vol. 1954, pp. 143–160. Springer, Heidelberg (2000)
Sawitzki, D.: Experimental studies of symbolic shortest-path algorithms. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA 2004. LNCS, vol. 3059, pp. 482–497. Springer, Heidelberg (2004)
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.: Implicit flow maximization on grid networks. Technical report, Universität Dortmund (2004)
Sawitzki, D.: Implicit maximization of flows over time. Technical report, Universität Dortmund (2004)
Sawitzki, D.: On graphs with characteristic bounded-width functions. Technical report, Universität Dortmund (2004)
Wegener, I.: Branching Programs and Binary Decision Diagrams. SIAM, Philadelphia (2000)
Woelfel, P.: The OBDD-size of cographs. Internal report, Universität Dortmund (2003)
Woelfel, P.: Symbolic topological sorting with oBDDs. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 671–680. Springer, Heidelberg (2003)
Xie, A., Beerel, P.A.: Implicit enumeration of strongly connected components. In: ICCAD 1999, pp. 37–40. ACM Press, New York (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sawitzki, D. (2004). A Symbolic Approach to the All-Pairs Shortest-Paths Problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30559-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-540-30559-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24132-4
Online ISBN: 978-3-540-30559-0
eBook Packages: Computer ScienceComputer Science (R0)