Treffer: Encoding partial orders through modular decomposition.

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 | S | 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. [ABSTRACT FROM AUTHOR]