TY - JOUR
T1 - On the Succinct Representation of Equivalence Classes
AU - El-Zein, Hicham
AU - Lewenstein, Moshe
AU - Munro, J. Ian
AU - Raman, Venkatesh
AU - Chan, Timothy M.
N1 - Funding Information:
This work was sponsored by the NSERC of Canada and the Canada Research Chairs Program.
Publisher Copyright:
© 2016, Springer Science+Business Media New York.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models.Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of ∑i=1n⌊ni⌋ is necessary and sufficient. In other words, lg n+ lg lg n+ O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of ⌈ lg n⌉ for the label length, if each vertex need not get a unique label.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set { 1 , … , n} , we first show that Θ(n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(1) time in the standard word RAM model. We also develop a dynamic structure that uses O(nlgn) bits to support equivalence queries and unions in O(lg n/ lg lg n) worst case time or O(α(n)) expected amortized time where α(n) is the inverse Ackermann function.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set { 1 , … , cn} for any constant c> 1 , we show that Θ(lg n) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O(1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.
AB - Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models.Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of ∑i=1n⌊ni⌋ is necessary and sufficient. In other words, lg n+ lg lg n+ O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of ⌈ lg n⌉ for the label length, if each vertex need not get a unique label.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set { 1 , … , n} , we first show that Θ(n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(1) time in the standard word RAM model. We also develop a dynamic structure that uses O(nlgn) bits to support equivalence queries and unions in O(lg n/ lg lg n) worst case time or O(α(n)) expected amortized time where α(n) is the inverse Ackermann function.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set { 1 , … , cn} for any constant c> 1 , we show that Θ(lg n) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O(1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.
KW - Equivalence classes
KW - Labeling schemes
KW - Succinct data structures
UR - http://www.scopus.com/inward/record.url?scp=84979965034&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979965034&partnerID=8YFLogxK
U2 - 10.1007/s00453-016-0192-1
DO - 10.1007/s00453-016-0192-1
M3 - Article
AN - SCOPUS:84979965034
VL - 78
SP - 1020
EP - 1040
JO - Algorithmica (New York)
JF - Algorithmica (New York)
SN - 0178-4617
IS - 3
ER -