Computational aspects of the 2-dimension of partially ordered sets

Abstract : A well-known method to represent a partially ordered set P (order for short) consists in associating to each element of P a subset of a ?xed set S = {1, . . . , k} such that the order relation coincides with subset inclusion. Such an embedding of P into 2S (the lattice of all subsets of S) is called a bit-vector encoding of P. In this article, we focus on computational complexity results. After a synthesis of known results, we come back on the NP-completeness by detailing a proof and enforcing the conclusion with non-approximability ratios. Besides this general result, we investigate the complexity of the 2-dimension for the class of trees. We describe a 4-approximation algorithm for this class. It uses an optimal balancing strategy which solves a conjecture of [KVH97]. Several interesting open problems are listed.
Mots-clés : ensemble ordonné
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2004, 312 (2-3), pp.401-431. 〈10.1016/j.tcs.2003.10.029〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00099966
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:12:57
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Lien texte intégral

Identifiants

Citation

Michel Habib, Lhouari Nourine, Olivier Raynaud, Eric Thierry. Computational aspects of the 2-dimension of partially ordered sets. Theoretical Computer Science, Elsevier, 2004, 312 (2-3), pp.401-431. 〈10.1016/j.tcs.2003.10.029〉. 〈inria-00099966〉

Partager

Métriques

Consultations de la notice

335