Document Open Access Logo

Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees

Authors Meng He , J. Ian Munro , Yakov Nekrich, Sebastian Wild , Kaiyu Wu

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.25.pdf
  • Filesize: 0.76 MB
  • 18 pages

Document Identifiers

Author Details

Meng He
  • Dalhousie University, Halifax, Canada
J. Ian Munro
  • University of Waterloo, Canada
Yakov Nekrich
  • Michigan Tech, Houghton, MI, USA
Sebastian Wild
  • University of Liverpool, UK
Kaiyu Wu
  • University of Waterloo, Canada

Funding

  • Munro, J. Ian: NSERC and the Canada Research Chairs Programme.

Cite As Get BibTex

Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 25:1-25:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.25

Abstract

We present the first succinct distance oracles for (unweighted) interval graphs and related classes of graphs, using a novel succinct data structure for ordinal trees that supports the mapping between preorder (i.e., depth-first) ranks and level-order (breadth-first) ranks of nodes in constant time. Our distance oracles for interval graphs also support navigation queries - testing adjacency, computing node degrees, neighborhoods, and shortest paths - all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well as mapping to and from level-order ranks and retrieving the last (first) internal node before (after) a given node in a level-order traversal, all in constant time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
  • Theory of computation → Data compression
Keywords
  • succinct data structures
  • distance oracles
  • ordinal tree
  • level order
  • breadth-first order
  • interval graphs
  • proper interval graphs
  • succinct graph representation

Metrics

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

Related Versions

References

  1. Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, and Srinivasa Rao Satti. Succinct data structures for families of interval graphs. In Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings, pages 1-13, 2019. URL: https://doi.org/10.1007/978-3-030-24766-9_1.
  2. Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, and Srinivasa Rao Satti. Succinct data structures for families of interval graphs, 2019. URL: http://arxiv.org/abs/1902.09228.
  3. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. In F. Frances Yao and Eugene M. Luks, editors, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA, pages 735-744. ACM, 2000. URL: https://doi.org/10.1145/335305.335410.
  4. Jérémy Barbay, Meng He, J. Ian Munro, and Srinivasa Rao Satti. Succinct indexes for strings, binary relations and multilabeled trees. ACM Transactions on Algorithms, 7:52:1-52:27, September 2011. URL: https://doi.org/10.1145/2000807.2000820.
  5. David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Representing trees of higher degree. Algorithmica, 43(4):275-292, 2005. URL: https://doi.org/10.1007/s00453-004-1146-6.
  6. Daniel K. Blandford, Guy E. Blelloch, and Ian A. Kash. Compact representations of separable graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 679-688, 2003. Google Scholar
  7. Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Succinct representations of planar maps. Theoretical Computer Science, 408(2-3):174-187, 2008. Google Scholar
  8. Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu. Orderly spanning trees with applications. SIAM Journal on Computing, 34(4):924-945, 2005. URL: https://doi.org/10.1137/S0097539702411381.
  9. Richie Chih-Nan Chuang, Ashim Garg, Xin He, Ming-Yang Kao, and Hsueh-I Lu. Compact encodings of planar graphs via canonical orderings and multiple parentheses. In Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pages 118-129, 1998. Google Scholar
  10. D. R. Clark and J. I. Munro. Efficient suffix trees on secondary storage. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 383-391, 1996. URL: https://doi.org/10.5555/313852.314087.
  11. Pooya Davoodi, Rajeev Raman, and Srinivasa Rao Satti. On succinct representations of binary trees. Mathematics in Computer Science, 11(2):177-189, March 2017. URL: https://doi.org/10.1007/s11786-017-0294-4.
  12. Arash Farzan and J. Ian Munro. Succinct representations of arbitrary graphs. In 16th Annual European Symposium on Algorithms, pages 393-404, 2008. Google Scholar
  13. Arash Farzan and J. Ian Munro. A uniform paradigm to succinctly encode various families of trees. Algorithmica, 68(1):16-40, June 2014. URL: https://doi.org/10.1007/s00453-012-9664-0.
  14. Arash Farzan, Rajeev Raman, and S. Srinivasa Rao. Universal succinct representations of trees? In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, volume 5555 of Lecture Notes in Computer Science, pages 451-462, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_38.
  15. Cyril Gavoille and Christophe Paul. Optimal distance labeling for interval graphs and related graph families. SIAM Journal on Discrete Mathematics, 22(3):1239-1258, January 2008. URL: https://doi.org/10.1137/050635006.
  16. Richard F. Geary, Rajeev Raman, and Venkatesh Raman. Succinct ordinal trees with level-ancestor queries. ACM Transactions on Algorithms, 2(4):510-534, October 2006. URL: https://doi.org/10.1145/1198513.1198516.
  17. Phil Hanlon. Counting interval graphs. Transactions of the American Mathematical Society, 272(2):383-383, February 1982. URL: https://doi.org/10.1090/s0002-9947-1982-0662044-8.
  18. Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu. Distance oracles for interval graphs via breadth-first rank/select in succinct trees, 2020. URL: http://arxiv.org/abs/2005.07644.
  19. Meng He, J. Ian Munro, and Srinivasa Satti Rao. Succinct ordinal trees based on tree covering. ACM Transactions on Algorithms, 8(4):1-32, September 2012. URL: https://doi.org/10.1145/2344422.2344432.
  20. Guy Jacobson. Space-efficient static trees and graphs. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 549-554, 1989. URL: https://doi.org/10.1109/SFCS.1989.63533.
  21. Jesper Jansson, Kunihiko Sadakane, and Wing-Kin Sung. Ultra-succinct representation of ordered trees with applications. Journal of Computer and System Sciences, 78(2):619-631, March 2012. URL: https://doi.org/10.1016/j.jcss.2011.09.002.
  22. Pavel Klavík, Yota Otachi, and Jiří Šejnoha. On the classes of interval graphs of limited nesting and count of lengths. Algorithmica, 81(4):1490-1511, April 2019. URL: https://doi.org/10.1007/s00453-018-0481-y.
  23. Hsueh-I Lu and Chia-Chi Yeh. Balanced parentheses strike back. ACM Transactions on Algorithms, 4:28:1-28:13, July 2008. URL: https://doi.org/10.1145/1367064.1367068.
  24. J. Ian Munro and Patrick K. Nicholson. Succinct posets. Algorithmica, 76(2):445-473, 2016. URL: https://doi.org/10.1007/s00453-015-0047-1.
  25. J. Ian Munro and Venkatesh Raman. Succinct representation of balanced parentheses and static trees. SIAM Journal on Computing, 31(3):762-776, January 2001. URL: https://doi.org/10.1137/s0097539799364092.
  26. J. Ian Munro, Venkatesh Raman, and S. Srinivasa Rao. Space efficient suffix trees. Journal of Algorithms, 39(2):205-222, 2001. URL: https://doi.org/10.1006/jagm.2000.1151.
  27. J. Ian Munro and S. Srinivasa Rao. Succinct representations of functions. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, pages 1006-1015, 2004. URL: https://doi.org/10.1007/978-3-540-27836-8_84.
  28. J. Ian Munro and Corwin Sinnamon. Time and space efficient representations of distributive lattices. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 550-567. SIAM, 2018. URL: https://doi.org/10.1137/1.9781611975031.36.
  29. J. Ian Munro and Kaiyu Wu. Succinct data structures for chordal graphs. In 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, pages 67:1-67:12, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.67.
  30. Gonzalo Navarro. Compact Data Structures - A practical approach. Cambridge University Press, 2016. Google Scholar
  31. Gonzalo Navarro and Kunihiko Sadakane. Fully functional static and dynamic succinct trees. ACM Transactions on Algorithms, 10(3):1-39, May 2014. URL: https://doi.org/10.1145/2601073.
  32. Mihai Patrascu. Succincter. In Symposium on Foundations of Computer Science (FOCS). IEEE, October 2008. URL: https://doi.org/10.1109/focs.2008.83.
  33. Mihai Patrascu and Liam Roditty. Distance oracles beyond the thorup-zwick bound. SIAM J. Comput., 43(1):300-311, 2014. URL: https://doi.org/10.1137/11084128X.
  34. R. Ravi, Madhav V. Marathe, and C. Pandu Rangan. An optimal algorithm to solve the all-pair shortest path problem on interval graphs. Networks, 22(1):21-35, 1992. URL: https://doi.org/10.1002/net.3230220103.
  35. Kunihiko Sadakane. Compressed suffix trees with full functionality. Theory of Computing Systems, 41(4):589-607, 2007. URL: https://doi.org/10.1007/s00224-006-1198-x.
  36. Gaurav Singh, N. S. Narayanaswamy, and G. Ramakrishna. Approximate distance oracle in o(n 2) time and o(n) space for chordal graphs. In M. Sohel Rahman and Etsuji Tomita, editors, WALCOM: Algorithms and Computation - 9th International Workshop, WALCOM 2015, Dhaka, Bangladesh, February 26-28, 2015. Proceedings, volume 8973 of Lecture Notes in Computer Science, pages 89-100. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-15612-5_9.
  37. Christian Sommer. Shortest-path queries in static networks. ACM Computing Surveys, 46(4):1-31, April 2014. URL: https://doi.org/10.1145/2530531.
  38. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: https://doi.org/10.1145/1044731.1044732.
  39. Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler, and Philip E. Bourne. An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Computer Applications in the Biosciences, 10(3):309-317, 1994. URL: https://doi.org/10.1093/bioinformatics/10.3.309.
  40. Uri Zwick. Exact and approximate distances in graphs - A survey. In Friedhelm Meyer auf der Heide, editor, Algorithms - ESA 2001, 9th Annual European Symposium, Aarhus, Denmark, August 28-31, 2001, Proceedings, volume 2161 of Lecture Notes in Computer Science, pages 33-48. Springer, 2001. URL: https://doi.org/10.1007/3-540-44676-1_3.
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