Simple 2f-Color Choice Dictionaries

DOI10.4230/LIPICS.ISAAC.2018.66MaRDI QIDQ5091061zbMATH OpenOpenAlexFDO

Authors Frank Kammer, Andrej Sajenko

Publication date 21 July 2022

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/10014/pdf/LIPIcs-ISAAC-2018-66.pdf/

zbMATH Keywords

space efficientsuccinctword RAM

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• A constant-time colored choice dictionary with almost robust iteration
• De Dictionariis Dynamicis Pauco Spatio Utentibus
• Nearly optimal static Las Vegas succinct dictionary
• Deterministic dictionaries
• A simple, fast, and compact static dictionary

Cites work

• A framework for in-place graph algorithms
• Depth-First Search Using O(n) Bits
• Improved space efficient algorithms for BFS, DFS and applications
• Optimal time-space tradeoff for the 2D convex-hull problem
• Priority queues and sorting for read-only data
• Space-efficient approximation scheme for maximum matching in sparse graphs
• Space-efficient basic graph algorithms
• Space-efficient biconnected components and recognition of outerplanar graphs
• Space-efficient Euler partition and bipartite edge coloring
• Space-efficient plane-sweep algorithms

Cited in

(5)

• Space-efficient vertex separators for treewidth
• A constant-time colored choice dictionary with almost robust iteration
• Sorting and ranking of self-delimiting numbers with applications to tree isomorphism
• Space-efficient graph coarsening with applications to succinct planar encodings
• Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism

This page was built for publication: Simple 2^f-Color Choice Dictionaries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091061)