Computer Science – Data Structures and Algorithms
Scientific paper
2012-04-09
Computer Science
Data Structures and Algorithms
12 pages lncs format + short appendix
Scientific paper
We describe an algorithm for compressing a partially ordered set, or \emph{poset}, so that it occupies space matching the information theory lower bound (to within lower order terms), in the worst case. Using this algorithm, we design a succinct data structure for representing a poset that, given two elements, can report whether one precedes the other in constant time. This is equivalent to succinctly representing the transitive closure graph of the poset, and we note that the same method can also be used to succinctly represent the transitive reduction graph. For an $n$ element poset, the data structure occupies $n^2/4 + o(n^2)$ bits, in the worst case, which is roughly half the space occupied by an upper triangular matrix. Furthermore, a slight extension to this data structure yields a succinct oracle for reachability in arbitrary directed graphs. Thus, using roughly a quarter of the space required to represent an arbitrary directed graph, reachability queries can be supported in constant time.
Munro Ian J.
Nicholson Patrick K.
No associations
LandOfFree
Succinct Posets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Succinct Posets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Posets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-652513