Research Article
Encoding Partial Orders Through Modular Decomposition
@INPROCEEDINGS{10.4108/eai.27-2-2017.152339, author={Laurent Beaudou and Kaoutar Ghazi and Giacomo Kahn and Olivier Raynaud and Eric Thierry}, title={Encoding Partial Orders Through Modular Decomposition}, proceedings={First EAI International Conference on Computer Science and Engineering}, publisher={EAI}, proceedings_a={COMPSE}, year={2017}, month={3}, keywords={Bit-vector encodings; 2-dimension; Modular decomposition Series-parallel partial orders; Embeddings; Heuristics}, doi={10.4108/eai.27-2-2017.152339} }- Laurent Beaudou
Kaoutar Ghazi
Giacomo Kahn
Olivier Raynaud
Eric Thierry
Year: 2017
Encoding Partial Orders Through Modular Decomposition
COMPSE
EAI
DOI: 10.4108/eai.27-2-2017.152339
Abstract
A well-known method to represent a partially ordered set P consists in associating to each element of P a subset of a fixed set S ={1,...,k} such that the order relation coincides with subset inclusion. Such an embedding is called a bit-vector encoding of P and is economical with space. As a consequence, they have found applications in knowledge representation, distributed computing or object-oriented programming. The smallest size of such an encoding is called the 2-dimension of P and its computation is known to be NP-hard in the general case [12]. Finding heuristics which provide compact encodings is challenging and it has yielded many works. Our paper presents a new heuristic through modular decomposition. This unified process is a 4-approximation for rooted trees 2-dimension and provides reduced encoding by 40% for series-parallel posets. It reaches or improves the best results for general posets.
