Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.

DOI10.4230/LIPIcs.MFCS.2018.65OpenAlexW2963202010MaRDI QIDQ5005169

Andrej Sajenko, Frank Kammer

Publication date: 4 August 2021

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

zbMATH Keywords

space efficiencydynamic graph representationsuccinct \(c\)-ary memory

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

In-place initializable arrays ⋮ Space-efficient vertex separators for treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reprint of: Memory-constrained algorithms for simple polygons
• Succinct encoding of arbitrary graphs
• Succinct representations of permutations and functions
• Space-efficient Euler partition and bipartite edge coloring
• Linear-time in-place DFS and BFS on the word RAM
• Low Redundancy in Static Dictionaries with Constant Query Time
• Changing base without losing space
• Depth-First Search Using $$O(n)$$ Bits
• Space-efficient Basic Graph Algorithms
• Space-Time Trade-offs for Stack-Based Algorithms
• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs
• Space-Efficient Plane-Sweep Algorithms.
• Dynamic entropy-compressed sequences and full-text indexes
• On-the-Fly Array Initialization in Less Space
• Spaces, Trees, and Colors

This page was built for publication: Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.