Optimal algorithms for list indexing and subset rank

DOI10.1007/3-540-51542-9_5MaRDI QIDQ4028873zbMATH OpenFDO

Authors Paul F. Dietz

Publication date 28 March 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1802/5694

zbMATH Keywords

list indexingsubset rank

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 910856
• Lower bounds for dynamic data structures on algebraic RAMs
• Lower bounds on the size of selection and rank indexes
• Optimal lower bounds for rank and select indexes
• Optimal bounds for the predecessor problem and related problems

Cited in

(35)

• A (slightly) faster algorithm for Klee's measure problem
• Fusion trees can be implemented with AC^0 instructions only
• Ranking and unranking permutations in linear time
• Partial evaluation in rank aggregation problems
• Dynamic relative compression, dynamic partial sums, and substring concatenation
• Sorting signed permutations by reversals, revisited
• Space-efficient B trees via load-balancing
• Linear-space data structures for range mode query in arrays
• Finding median in read-only memory on integer input
• Succinct data structure for dynamic trees with faster queries
• Dynamic range majority data structures
• List Factoring and Relative Worst Order Analysis
• Approximate Indexed Lists
• scientific article; zbMATH DE number 910856 (Why is no real title available?)
• Improved time and space bounds for dynamic range mode
• Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
• Lower bounds for dynamic algorithms
• Dynamic algorithms for the Dyck languages
• Fast dynamic arrays
• Succinct partial sums and Fenwick trees
• Counting palindromes in substrings
• Syntactic view of sigma-tau generation of permutations
• Partial sums on the ultra-wide word RAM
• New algorithms and bounds for halving pseudolines
• scientific article; zbMATH DE number 7765406 (Why is no real title available?)
• A compact data structure and parallel algorithms for permutation graphs
• Random access in persistent strings and segment selection
• Optimal resizable arrays
• Dynamic data structures for approximate Hausdorff distance in the word RAM
• Space-efficient B trees via load-balancing
• (Worst-case) optimal adaptive dynamic bitvectors
• Succinct data structures for searchable partial sums with optimal worst-case performance
• A new family of randomized algorithms for list accessing
• A quantitative study of pure parallel processes
• Computing distances between partial rankings

This page was built for publication: Optimal algorithms for list indexing and subset rank

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