HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 10:12:57 AM
Last modification on : Friday, February 4, 2022 - 3:19:37 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

315