Search Results

Documents authored by Hagerup, Torben

Document
DOI: 10.4230/LIPIcs.MFCS.2019.64
A Constant-Time Colored Choice Dictionary with Almost Robust Iteration

Authors: Torben Hagerup

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
A (colored) choice dictionary is a data structure that is initialized with positive integers n and c and subsequently maintains a sequence of n elements of {0,...,c-1}, called colors, under operations to inspect and to update the color in a given position and to return the position of an occurrence of a given color. Choice dictionaries are fundamental in space-efficient computing. Some applications call for the additional operation of dynamic iteration, i.e., enumeration of the positions containing a given color while the sequence of colors may change. An iteration is robust if it enumerates every position that contains the relevant color throughout the iteration but never enumerates a position more than once or when it does not contain the color in question. We describe the first choice dictionary that executes every operation in constant amortized time and almost robust iteration in constant amortized time per element enumerated. The iteration is robust, except that it may enumerate some elements a second time. The data structure occupies n log_2 c+O((log n)^2) bits. The time and space bounds assume that c=O((log n)^{1/2}(log log n)^{-{3/2}}).
Cite as

Torben Hagerup. A Constant-Time Colored Choice Dictionary with Almost Robust Iteration. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hagerup:LIPIcs.MFCS.2019.64,
  author =	{Hagerup, Torben},
  title =	{{A Constant-Time Colored Choice Dictionary with Almost Robust Iteration}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.64},
  URN =		{urn:nbn:de:0030-drops-110083},
  doi =		{10.4230/LIPIcs.MFCS.2019.64},
  annote =	{Keywords: Succinct data structures, space efficiency, in-place chain technique, bounded universes, amortization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.44
On-the-Fly Array Initialization in Less Space

Authors: Torben Hagerup and Frank Kammer

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We show that for all given n,t,w in {1,2,...} with n<2^w, an array of n entries of w bits each can be represented on a word RAM with a word length of w bits in at most nw+ceil(n(t/(2 w))^t) bits of uninitialized memory to support constant-time initialization of the whole array and O(t)-time reading and writing of individual array entries. At one end of this tradeoff, we achieve initialization and access (i.e., reading and writing) in constant time with nw+ceil(n/w^t) bits for arbitrary fixed t, to be compared with nw+Theta(n) bits for the best previous solution, and at the opposite end, still with constant-time initialization, we support O(log n)-time access with just nw+1 bits, which is optimal for arbitrary access times if the initialization executes fewer than n steps.
Cite as

Torben Hagerup and Frank Kammer. On-the-Fly Array Initialization in Less Space. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 44:1-44:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hagerup_et_al:LIPIcs.ISAAC.2017.44,
  author =	{Hagerup, Torben and Kammer, Frank},
  title =	{{On-the-Fly Array Initialization in Less Space}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{44:1--44:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.44},
  URN =		{urn:nbn:de:0030-drops-82527},
  doi =		{10.4230/LIPIcs.ISAAC.2017.44},
  annote =	{Keywords: data structures, space efficiency, constant-time initialization, on-the-fly initialization, arrays}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.288
Space-efficient Basic Graph Algorithms

Authors: Amr Elmasry, Torben Hagerup, and Frank Kammer

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We reconsider basic algorithmic graph problems in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. For computing connected components and performing breadth-first search, we match the running times of standard algorithms that have no memory restrictions, for depth-first search and related problems we come within a factor of \Theta(\log\log n), and for computing minimum spanning forests and single-source shortest-paths trees we come close for sparse input graphs.
Cite as

Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 288-301, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{elmasry_et_al:LIPIcs.STACS.2015.288,
  author =	{Elmasry, Amr and Hagerup, Torben and Kammer, Frank},
  title =	{{Space-efficient Basic Graph Algorithms}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{288--301},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.288},
  URN =		{urn:nbn:de:0030-drops-49217},
  doi =		{10.4230/LIPIcs.STACS.2015.288},
  annote =	{Keywords: graph algorithms, depth-first search, single-source shortest paths, register input model}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1350
Trimming of Graphs, with Application to Point Labeling

Authors: Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
For $t,g>0$, a vertex-weighted graph of total weight $W$ is $(t,g)$-trimmable if it contains a vertex-induced subgraph of total weight at least $(1-1/t)W$ and with no simple path of more than $g$ edges. A family of graphs is trimmable if for each constant $t>0$, there is a constant $g=g(t)$ such that every vertex-weighted graph in the family is $(t,g)$-trimmable. We show that every family of graphs of bounded domino treewidth is trimmable. This implies that every family of graphs of bounded degree is trimmable if the graphs in the family have bounded treewidth or are planar. Based on this result, we derive a polynomial-time approximation scheme for the problem of labeling weighted points with nonoverlapping sliding labels of unit height and given lengths so as to maximize the total weight of the labeled points. This settles one of the last major open questions in the theory of map labeling.
Cite as

Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, and Alexander Wolff. Trimming of Graphs, with Application to Point Labeling. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 265-276, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.STACS.2008.1350,
  author =	{Erlebach, Thomas and Hagerup, Torben and Jansen, Klaus and Minzlaff, Moritz and Wolff, Alexander},
  title =	{{Trimming of Graphs, with Application to Point Labeling}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{265--276},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1350},
  URN =		{urn:nbn:de:0030-drops-13509},
  doi =		{10.4230/LIPIcs.STACS.2008.1350},
  annote =	{Keywords: Trimming weighted graphs, domino treewidth, planar graphs, point-feature label placement, map labeling, polynomial-time approximation schemes}
}
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