Document Open Access Logo

Indexing Graph Search Trees and Applications

Authors Sankardeep Chakraborty, Kunihiko Sadakane

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.67.pdf
  • Filesize: 450 kB
  • 14 pages

Document Identifiers

Author Details

Sankardeep Chakraborty
  • RIKEN Center for Advanced Intelligence Project, Japan
Kunihiko Sadakane
  • The University of Tokyo, Japan

Funding

This work was partially supported by JST CREST Grant Number JPMJCR1402, Japan.

Cite As Get BibTex

Sankardeep Chakraborty and Kunihiko Sadakane. Indexing Graph Search Trees and Applications. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.67

Abstract

We consider the problem of compactly representing the Depth First Search (DFS) tree of a given undirected or directed graph having n vertices and m edges while supporting various DFS related queries efficiently in the RAM with logarithmic word size. We study this problem in two well-known models: indexing and encoding models. While most of these queries can be supported easily in constant time using O(n lg n) bits of extra space, our goal here is, more specifically, to beat this trivial O(n lg n) bit space bound, yet not compromise too much on the running time of these queries. In the indexing model, the space bound of our solution involves the quantity m, hence, we obtain different bounds for sparse and dense graphs respectively. In the encoding model, we first give a space lower bound, followed by an almost optimal data structure with extremely fast query time. Central to our algorithm is a partitioning of the DFS tree into connected subtrees, and a compact way to store these connections. Finally, we also apply these techniques to compactly index the shortest path structure, biconnectivity structures among others.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Depth First Search Tree
  • Compact Data Structures
  • Encoding Schemes

Metrics

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

References

  1. H. Acan, S. Chakraborty, S. Jo, and S. R. Satti. Succinct Data Structures for Families of Interval Graphs. In WADS, 2019. Google Scholar
  2. N. Banerjee, S. Chakraborty, V. Raman, and S. R. Satti. Space Efficient Linear Time Algorithms for BFS, DFS and Applications. Theory of Computing Systems, 2018. Google Scholar
  3. J. Barbay, L. C. Aleardi, M. He, and J. I. Munro. Succinct Representation of Labeled Graphs. In 18th ISAAC, pages 316-328, 2007. Google Scholar
  4. M. A. Bender and M. Farach-Colton. The Level Ancestor Problem simplified. Theor. Comput. Sci., 321(1):5-12, 2004. URL: https://doi.org/10.1016/j.tcs.2003.05.002.
  5. D. K. Blandford, G. E. Blelloch, and I. A. Kash. Compact representations of separable graphs. In 14th SODA, pages 679-688, 2003. Google Scholar
  6. S. Chakraborty. Space Efficient Graph Algorithms. PhD thesis. The Institute of Mathematical Sciences, HBNI, India, 2018. Google Scholar
  7. S. Chakraborty, S. Jo, and S. R. Satti. Improved Space-efficient Linear Time Algorithms for Some Classical Graph Problems. CoRR, abs/1712.03349, 2017. URL: http://arxiv.org/abs/1712.03349.
  8. S. Chakraborty, A. Mukherjee, V. Raman, and S. R. Satti. A Framework for In-place Graph Algorithms. In 26th ESA, pages 13:1-13:16, 2018. Google Scholar
  9. S. Chakraborty, V. Raman, and S. R. Satti. Biconnectivity, st-numbering and other applications of DFS using O(n) bits. J. Comput. Syst. Sci., 90:63-79, 2017. Google Scholar
  10. S. Chakraborty and S. R. Satti. Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS. J. Comb. Optim., 37(2):465-481, 2019. Google Scholar
  11. D. Clark. Compact Pat Trees. PhD thesis. University of Waterloo, Canada, 1996. Google Scholar
  12. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  13. S. Even and R. E. Tarjan. Computing an st -Numbering. Theor. Comput. Sci., 2(3):339-344, 1976. Google Scholar
  14. A. Farzan and J. I. Munro. Succinct representation of dynamic trees. Theor. Comput. Sci., 412(24):2668-2678, 2011. Google Scholar
  15. A. Farzan and J. I. Munro. A Uniform Paradigm to Succinctly Encode Various Families of Trees. Algorithmica, 68(1):16-40, 2014. Google Scholar
  16. L. Ferres, J. F. Sepúlveda, T. Gagie, M. He, and G. Navarro. Fast and Compact Planar Embeddings. In 15th WADS, pages 385-396, 2017. Google Scholar
  17. J. E. Hopcroft and R. E. Tarjan. Efficient Planarity Testing. J. ACM, 21(4):549-568, 1974. Google Scholar
  18. J. I. Munro and P. K. Nicholson. Compressed Representations of Graphs. In Encyclopedia of Algorithms, pages 382-386. Springer, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_646.
  19. J. I. Munro, R. Raman, V. Raman, and S. S. Rao. Succinct representations of permutations and functions. Theor. Comput. Sci., 438:74-88, 2012. Google Scholar
  20. J. I. Munro and V. Raman. Succinct Representation of Balanced Parentheses and Static Trees. SIAM J. Comput., 31(3):762-776, 2001. Google Scholar
  21. G. Navarro. Compact Data Structures - A Practical Approach. Cambridge University Press, 2016. URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/compact-data-structures-practical-approach?format=HB.
  22. R. E. Tarjan. Depth-First Search and Linear Graph Algorithms. SIAM J. Comput., 1(2):146-160, 1972. Google Scholar
  23. R. E. Tarjan. A Note on Finding the Bridges of a Graph. Information Processing Letters, 2(6):160-161, 1974. Google Scholar
  24. R. E. Tarjan. Finding Dominators in Directed Graphs. SIAM J. Comput., 3(1):62-89, 1974. Google Scholar
  25. K. Yamanaka and S. Nakano. A compact encoding of plane triangulations with efficient query supports. Inf. Process. Lett., 110(18-19):803-809, 2010. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact