2011 | OriginalPaper | Buchkapitel
Compact Representation of Posets
verfasst von : Arash Farzan, Johannes Fischer
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We give a data structure for storing an
n
-element poset of width
w
in essentially minimal space. We then show how this data structure supports the most interesting queries on posets in either constant time, or in time that depends only on
w
and the size of the in-/output, but not on
n
. Our results also have direct applicability to DAGs of low width.