Succinct posets

DOI10.1007/978-3-642-33090-2_64MaRDI QIDQ2912889zbMATH OpenOpenAlexFDO

Authors J. Ian Munro, Patrick K. Nicholson

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1957

Mathematics Subject Classification ID

Partial orders, general (06A06) Data structures (68P05) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: 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.

Recommendations

• Succinct posets
• Compact representation of posets
• Succinct Representations of Arbitrary Graphs
• Succinct representations of ordinal trees
• Fully-functional succinct trees

Cited in

(6)

• Localized and compact data-structure for comparability graphs
• On the succinct representation of equivalence classes
• Succinct data structures for representing equivalence classes
• scientific article; zbMATH DE number 4047144 (Why is no real title available?)
• Succinct posets
• Compact representation of posets

This page was built for publication: Succinct posets

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