.png){kind=icon}
返回
Encoding partial orders through modular decomposition
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jocs.2017.05.008.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Let P be a poset and S be a set of elements. A well-known method for representing P is called a bit vector encoding and consists in associating to each element of P a subset of S such that the order relation between two elements coincides with their subsets inclusion. The size of this encoding is 'SI and it determines both space and time needed to store and compare the poset's elements. As a consequence, this encoding has found applications for handling hierarchies in databases, distributed computing, object oriented programming languages, etc. The computation of the smallest size of a bit-vector encoding of a poset, called the 2-dimension, is an NP-hard problem. Thus, researches deal with heuristics that provide tight bounds or an approximation of this parameter. Our paper introduces new classes of trees whose the 2-dimension is either known or 2-approximated. Moreover, it presents a new heuristic for partial orders encoding through the modular decomposition. This unified process is a 4-approximation for the 2-dimension of rooted trees and provides reduced encoding by almost 40% for series-parallel posets. It reaches or improves the best results for general posets. (C) 2017 Elsevier B.V. All rights reserved.
Keyword:
Bit-vector encodings
2-Dimension
Modular decomposition
Series-parallel partial orders
Embeddings
Heuristics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
18.3
论文数:
3.1K
被引数:
4.0K
机构
引用论文
.png){kind=icon}
Biotization and in vitro plant cell cultures: plant endophyte strategy in response to heavy metals knowledge in assisted phytoremediation生物矿化作用与植物细胞离体培养：植物内生菌策略及其在辅助植物修复中对重金属知识的响应
PREAI
分享收藏Identification of key candidate tumor biomarkers in non‑small‑cell lung cancer by in silico analysis通过计算机分析鉴定非小细胞肺癌中的关键候选肿瘤生物标志物
OAAI
OAAI分享收藏
查看更多内容