Algorithms for a Bit-Vector Encoding of Trees

Ghazi K., Beaudou L., Raynaud O.

1st International Conference on Intelligent Computing and Optimization (ICO), Pattaya, Thailand, 4 - 05 October 2018, vol.866, pp.418-427 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 866
  • Doi Number: 10.1007/978-3-030-00979-3_44
  • City: Pattaya
  • Country: Thailand
  • Page Numbers: pp.418-427
  • Middle East Technical University Affiliated: No


A bit-vector encoding is a well known method for representing hierarchies (i. e. partially ordered sets). This encoding corresponds to an embedding of a given hierarchy into a Boolean lattice whose dimension is the encoding's size. Computing an optimal bit-vector encoding, which size is called the 2-dimension, is an NP-hard problem. Hence, many algorithms were designed to provide good bit-vector encoding. In this paper, we study tree hierarchies. We analyse previous algorithms for their bit-vector encoding then we point out their common strategy that led us to design a new algorithm improving all the previous ones.