Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits

Authors Sankardeep Chakraborty, Venkatesh Raman, Srinivasa Rao Satti



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.22.pdf
  • Filesize: 453 kB
  • 13 pages

Document Identifiers

Author Details

Sankardeep Chakraborty
Venkatesh Raman
Srinivasa Rao Satti

Cite AsGet BibTex

Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, Chain Decomposition and st-Numbering Using O(n) Bits. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.22

Abstract

Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014) reconsidered classical fundamental graph algorithms focusing on improving the space complexity. Elmasry et al. gave, among others, an implementation of depth first search (DFS) of a graph on n vertices and m edges, taking O(m lg lg n) time using O(n) bits of space improving on the time bound of O(m lg n) due to Asano et al. Subsequently Banerjee et al. (COCOON 2016) gave an O(m + n) time implementation using O(m+n) bits, for DFS and its classical applications (including testing for biconnectivity, and finding cut vertices and cut edges). Recently, Kammer et al. (MFCS 2016) gave an algorithm for testing biconnectivity using O(n + min{m, n lg lg n}) bits in linear time. In this paper, we consider O(n) bits implementations of the classical applications of DFS. These include the problem of finding cut vertices, and biconnected components, chain decomposition and st-numbering. Classical algorithms for them typically use DFS and some Omega(lg n) bits of information at each node. Our O(n)-bit implementations for these problems take O(m lg^c n lg lg n) time for some small constant c (c leq 3). Central to our implementation is a succinct representation of the DFS tree and a space efficient partitioning of the DFS tree into connected subtrees, which maybe of independent interest for space efficient graph algorithms.
Keywords
  • biconnectivity
  • st-number
  • chain decomposition
  • tree cover
  • space efficient algorithms
  • read-only memory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. T. Asano, T. Izumi, M. Kiyomi, M. Konagaya, H. Ono, Y. Otachi, P. Schweitzer, J. Tarui, and R. Uehara. Depth-first search using O(n) bits. In 25th ISAAC, pages 553-564, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_44.
  2. T. Asano, D. G. Kirkpatrick, K. Nakagawa, and O. Watanabe. Õ(√n)-space and polynomial-time algorithm for planar directed graph reachability. In 39th MFCS LNCS 8634, pages 45-56, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_5.
  3. N. Banerjee, S. Chakraborty, and V. Raman. Improved space efficient algorithms for BFS,DFS and applications. In 22nd COCOON, volume 9797, pages 119-130. Springer, 2016. Google Scholar
  4. N. Banerjee, S. Chakraborty, V. Raman, S. Roy, and S. Saurabh. Time-space tradeoffs for dynamic programming in trees and bounded treewidth graphs. In 21st COCOON, volume 9198 of LNCS, pages 349-360. Springer, 2015. Google Scholar
  5. L. Barba, M. Korman, S. Langerman, K. Sadakane, and R. I. Silveira. Space-time trade-offs for stack-based algorithms. Algorithmica, 72(4):1097-1129, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9893-5.
  6. L. Barba, M. Korman, S. Langerman, and R. I. Silveira. Computing a visibility polygon using few variables. Comput. Geom., 47(9):918-926, 2014. URL: http://dx.doi.org/10.1016/j.comgeo.2014.04.001.
  7. G. Barnes, J. Buss, W. Ruzzo, and B. Schieber. A sublinear space, polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273-1282, 1998. URL: http://dx.doi.org/10.1137/S0097539793283151.
  8. U. Brandes. Eager st-ordering. In 10th ESA, pages 247-256, 2002. URL: http://dx.doi.org/10.1007/3-540-45749-6_25.
  9. D. Chakraborty, A. Pavan, R. Tewari, N. V. Vinodchandran, and L. Yang. New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs. In FSTTCS, pages 585-595, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.585.
  10. S. Chakraborty, V. Raman, and S. R. Satti. Biconnectivity, chain decomposition and st-numbering using O(n) bits. CoRR, abs/1606.08645, 2016. URL: http://arxiv.org/abs/1606.08645.
  11. D. R. Clark. Compact Pat Trees. PhD thesis. University of Waterloo, Canada, 1996. Google Scholar
  12. S. Datta, N. Limaye, P. Nimbhorkar, T. Thierauf, and F. Wagner. Planar graph isomorphism is in log-space. In 24th CCC, pages 203-214, 2009. URL: http://dx.doi.org/10.1109/CCC.2009.16.
  13. M. E. Dyer and A. M. Frieze. On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics, 10(2):139-153, 1985. Google Scholar
  14. J. Ebert. st-ordering the vertices of biconnected graphs. Computing, 30(1):19-33, 1983. URL: http://dx.doi.org/10.1007/BF02253293.
  15. M. Elberfeld, A. Jakoby, and T. Tantau. Logspace versions of the theorems of bodlaender and courcelle. In 51th FOCS, pages 143-152, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
  16. A. Elmasry, T. Hagerup, and F. Kammer. Space-efficient basic graph algorithms. In 32nd STACS, pages 288-301, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  17. S. Even and R. E. Tarjan. Computing an st-numbering. Theo. Comp. Sci., 2(3):339-344, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90086-4.
  18. A. Farzan and J. Ian Munro. Succinct representation of dynamic trees. Theor. Comput. Sci., 412(24):2668-2678, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2010.10.030.
  19. A. Farzan, R. Raman, and S. S. Rao. Universal succinct representations of trees? In 36th ICALP, pages 451-462, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02927-1_38.
  20. G. N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci., 34(1):19-26, 1987. URL: http://dx.doi.org/10.1016/0022-0000(87)90002-X.
  21. R. F. Geary, R. Raman, and V. Raman. Succinct ordinal trees with level-ancestor queries. ACM Trans. Algorithms, 2(4):510-534, 2006. URL: http://dx.doi.org/10.1145/1198513.1198516.
  22. E. Győri. Partition conditions and vertex-connectivity of graphs. Combinatorica, 1(3):263-273, 1981. Google Scholar
  23. M. He, J. I. Munro, and S. R. Satti. Succinct ordinal trees based on tree covering. ACM Trans. Algorithms, 8(4):42, 2012. URL: http://dx.doi.org/10.1145/2344422.2344432.
  24. F. Kammer, D. Kratsch, and M. Laudahn. Space-efficient biconnected components and recognition of outerplanar graphs. In 41st MFCS, 2016. Google Scholar
  25. L. Lovasz. A homology theory for spanning tress of a graph. Acta Mathematica Hungarica, 30(3-4):241-251, 1977. Google Scholar
  26. J. I. Munro and M. Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12:315-323, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90061-4.
  27. J. I. Munro and V. Raman. Selection from read-only memory and sorting with minimum data movement. Theor. Comput. Sci., 165(2):311-323, 1996. URL: http://dx.doi.org/10.1016/0304-3975(95)00225-1.
  28. J. I. Munro and V. Raman. Succinct representation of balanced parentheses and static trees. SIAM J. Comput., 31(3):762-776, 2001. URL: http://dx.doi.org/10.1137/S0097539799364092.
  29. S. Nakano, M. S. Rahman, and T. Nishizeki. A linear-time algorithm for four-partitioning four-connected planar graphs. Inf. Process. Lett., 62(6):315-322, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00083-5.
  30. O. Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008. URL: http://dx.doi.org/10.1145/1391289.1391291.
  31. J. M. Schmidt. Structure and constructions of 3-connected graphs. PhD thesis, Free University of Berlin, 2010. URL: http://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000022941.
  32. J. M. Schmidt. A simple test on 2-vertex- and 2-edge-connectivity. Inf. Process. Lett., 113(7):241-244, 2013. URL: http://dx.doi.org/10.1016/j.ipl.2013.01.016.
  33. J. M. Schmidt. The mondshein sequence. In 41st ICALP, pages 967-978, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_80.
  34. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. URL: http://dx.doi.org/10.1137/0201010.
  35. R. E. Tarjan. Two streamlined depth-first search algorithms. Fund. Inf., 9:85-94, 1986. Google Scholar
  36. M. Tompa. Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. SIAM J. Comput., 11(1):130-137, 1982. URL: http://dx.doi.org/10.1137/0211010.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail