Paper Info
Title
Compact representation of posets
Abstract
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.
Year
DOI
Venue
2011
10.1007/978-3-642-25591-5_32
ISAAC
Keywords
Field
DocType
n-element poset,minimal space,direct applicability,width w,compact representation,interesting query,constant time,low width,data structure
Data structure,Discrete mathematics,Combinatorics,Transitive reduction,Directed acyclic graph,Star product,Transitive closure,Mathematics,Partially ordered set
Conference
Volume
ISSN
Citations 
7074
0302-9743
3
PageRank 
References 
Authors
0.39
10
2
Name
Order
Citations
PageRank
Arash Farzan113611.07
Johannes Fischer221017.41