Succinct posets

DOI10.1007/978-3-642-33090-2_64zbMATH Open1346.68075arXiv1204.1957OpenAlexW2914551285MaRDI QIDQ2912889FDOQ2912889

Authors: J. Ian Munro, Patrick K. Nicholson 

Publication date: 25 September 2012

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

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.

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

Recommendations

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

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)

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
• Title not available (Why is that?)
• 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)