Algorithms for a Bit-Vector Encoding of Trees

Ghazi K., Beaudou L., Raynaud O.

1st International Conference on Intelligent Computing and Optimization (ICO), Pattaya, Tayland, 4 - 05 Ekim 2018, cilt.866, ss.418-427 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 866
  • Doi Numarası: 10.1007/978-3-030-00979-3_44
  • Basıldığı Şehir: Pattaya
  • Basıldığı Ülke: Tayland
  • Sayfa Sayıları: ss.418-427
  • Orta Doğu Teknik Üniversitesi Adresli: Hayır

Özet

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.