On the succinct representation of equivalence classes

DOI10.1007/S00453-016-0192-1MaRDI QIDQ2408100zbMATH OpenOpenAlexFDO

Authors Hicham El-Zein, Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, Timothy M. Chan

Publication date 9 October 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10012/8999

zbMATH Keywords

equivalence classeslabeling schemessuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Succinct data structures for representing equivalence classes
• Tradeoff between label space and auxiliary space for representation of equivalence classes
• Succinct Representation of Labeled Graphs
• Succinct representation of labeled graphs
• On the succinct representation of unlabeled permutations

Cites work

• A uniform paradigm to succinctly encode various families of trees
• Compact representations of ordered sets
• Compressed data structures: Dictionaries and data-aware measures
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Fusion trees can be implemented with AC^0 instructions only
• scientific article; zbMATH DE number 2079400 (Why is no real title available?)
• Implicat Representation of Graphs
• Labeling Schemes for Flow and Connectivity
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Membership in Constant Time and Almost-Minimum Space
• More haste, less waste: lowering the redundancy in fully indexable dictionaries
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• Radix Sorting with No Extra Space
• Representing trees of higher degree
• Space efficient suffix trees
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct ordinal trees with level-ancestor queries
• Succinct posets
• Succinct Representation of Labeled Graphs
• Succinct Representations of Arbitrary Graphs
• Surpassing the information theoretic bound with fusion trees
• The design of dynamic data structures
• Universal codeword sets and representations of the integers
• Worst-case and amortised optimality in union-find (extended abstract)

Cited in

(9)

• The intersection of the similarity and conjunctivity equivalence classes
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Lower bounds for protrusion replacement by counting equivalence classes
• A quick proof on the equivalence classes of extended Vogan diagrams
• Succinct data structures for representing equivalence classes
• Tradeoff between label space and auxiliary space for representation of equivalence classes
• Distance queries over dynamic interval graphs
• Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs
• Distance queries over dynamic interval graphs

This page was built for publication: On the succinct representation of equivalence classes

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