Compact Representation of Posets
Compact Representation of Posets
复制标题
集合的紧凑表示
DOI：
10.1007/978-3-642-25591-5_32
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Fischer
中科院分区：
文献类型：
--
作者：
Arash Farzan;J. Fischer
给出了在本质极小空间中存储宽度为w的n元偏序集的一种数据结构。然后，我们展示了这个数据结构如何支持最有趣的查询偏序集在恒定的时间，或在时间上只取决于w和大小的in-/输出，但不对n。我们的结果也有直接适用于低宽度的DAG。
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.