.png){kind=icon}
.png){kind=icon}
Return
Encoding partial orders through modular decomposition
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jocs.2017.05.008.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Bit-vector encodings
2-Dimension
Modular decomposition
Series-parallel partial orders
Embeddings
Heuristics
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
18.3
Papers:
3.1K
Citations:
4.0K