On-the-Fly Array Initialization in Less Space

DOI10.4230/LIPIcs.ISAAC.2017.44zbMath1457.68074arXiv1709.10477OpenAlexW2963670382MaRDI QIDQ5136264

Torben Hagerup, Frank Kammer

Publication date: 25 November 2020

Full work available at URL: https://arxiv.org/abs/1709.10477

zbMATH Keywords

data structuresarraysspace efficiencyconstant-time initializationon-the-fly initialization

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (3)

In-place initializable arrays ⋮ Space-efficient vertex separators for treewidth ⋮ Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.

Cites Work

• Unnamed Item
• An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• An implicit data structure for searching a multikey table in logarithmic time
• Surpassing the information theoretic bound with fusion trees
• No sorting? better searching!
• Spaces, Trees, and Colors
• Space-Efficient Euler Partition and Bipartite Edge Coloring

This page was built for publication: On-the-Fly Array Initialization in Less Space