Skip to Main content Skip to Navigation
Journal articles

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.
Keywords : ordered sets
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00099966
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 10:12:57 AM
Last modification on : Wednesday, April 21, 2021 - 8:52:05 AM

Links full text

Identifiers

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⟩

Share

Metrics

Record views

476