Document Open Access Logo

Simple 2^f-Color Choice Dictionaries

Authors Frank Kammer, Andrej Sajenko

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.66.pdf
  • Filesize: 476 kB
  • 12 pages

Document Identifiers

Author Details

Frank Kammer
  • THM, University of Applied Sciences Mittelhessen, Germany
Andrej Sajenko
  • THM, University of Applied Sciences Mittelhessen, Germany

Funding

  • Sajenko, Andrej: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 379157101.

Cite AsGet BibTex

Frank Kammer and Andrej Sajenko. Simple 2^f-Color Choice Dictionaries. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.66

Abstract

A c-color choice dictionary of size n in N is a fundamental data structure in the development of space-efficient algorithms that stores the colors of n elements and that supports operations to get and change the color of an element as well as an operation choice that returns an arbitrary element of that color. For an integer f>0 and a constant c=2^f, we present a word-RAM algorithm for a c-color choice dictionary of size n that supports all operations above in constant time and uses only nf+1 bits, which is optimal if all operations have to run in o(n/w) time where w is the word size. In addition, we extend our choice dictionary by an operation union without using more space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • space efficient
  • succinct
  • word RAM

Metrics

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

References

  1. Tetsuo Asano, Amr Elmasry, and Jyrki Katajainen. Priority Queues and Sorting for Read-Only Data. In Proc. 10th International Conference on Theory and Applications of Models of Computation (TAMC 2013), volume 7876 of LNCS, pages 32-41. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38236-9_4.
  2. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-First Search Using O(n) Bits. In Proc. 25th International Symposium on Algorithms and Computation (ISAAC 2014), volume 8889 of LNCS, pages 553-564. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_44.
  3. Niranka Banerjee, Sankardeep Chakraborty, and Venkatesh Raman. Improved Space Efficient Algorithms for BFS, DFS and Applications. In Proc. 22nd International Conference on Computing and Combinatorics (COCOON), volume 9797 of LNCS, pages 119-130. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-42634-1_10.
  4. Sankardeep Chakraborty, Anish Mukherjee, Venkatesh Raman, and Srinivasa Rao Satti. A Framework for In-place Graph Algorithms. In Proc. 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of LIPIcs, pages 13:1-13:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  5. Omar Darwish and Amr Elmasry. Optimal Time-Space Tradeoff for the 2D Convex-Hull Problem. In Proc. 22nd Annual European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 284-295. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_24.
  6. Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of LIPIcs, pages 28:1-28:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.28.
  7. Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of LIPIcs, pages 288-301. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  8. Amr Elmasry and Frank Kammer. Space-Efficient Plane-Sweep Algorithms. In Proc. 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 of LIPIcs, pages 30:1-30:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.30.
  9. Torben Hagerup. An Optimal Choice Dictionary. CoRR, abs/1711.00808, 2017. URL: http://arxiv.org/abs/1711.00808.
  10. Torben Hagerup. Small Uncolored and Colored Choice Dictionaries. CoRR, abs/1809.07661, 2018. URL: http://arxiv.org/abs/1809.07661.
  11. Torben Hagerup and Frank Kammer. Succinct Choice Dictionaries. CoRR, abs/1604.06058, 2016. URL: http://arxiv.org/abs/1604.06058.
  12. Torben Hagerup, Frank Kammer, and Moritz Laudahn. Space-efficient Euler partition and bipartite edge coloring. Theor. Comput. Sci., 2018. URL: http://dx.doi.org/10.1016/j.tcs.2018.01.008.
  13. Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. Algorithmica, 2018. URL: http://dx.doi.org/10.1007/s00453-018-0464-z.
  14. Frank Kammer and Andrej Sajenko. Space efficient (graph) algorithms. https://github.com/thm-mni-ii/sea, 2018.
  15. Takashi Katoh and Keisuke Goto. In-Place Initializable Arrays. CoRR, abs/1709.08900, 2017. URL: http://arxiv.org/abs/1709.08900.
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 Imprint Privacy Contact