Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Kammer, Frank; Sajenko, Andrej http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-100141
URL:

;

Simple 2^f-Color Choice Dictionaries

pdf-format:


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.

BibTeX - Entry

@InProceedings{kammer_et_al:LIPIcs:2018:10014,
  author =	{Frank Kammer and Andrej Sajenko},
  title =	{{Simple 2^f-Color Choice Dictionaries}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10014},
  URN =		{urn:nbn:de:0030-drops-100141},
  doi =		{10.4230/LIPIcs.ISAAC.2018.66},
  annote =	{Keywords: space efficient, succinct, word RAM}
}

Keywords: space efficient, succinct, word RAM
Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI