Séminaire Mathématique de Béjaia
Volume 11, Numéro 1, Pages 39-41
2012-12-31

Embedding Balanced Binary Trees In Hypercube



Auteurs : Kabyl Kamal .

Résumé

The hypercube is a structure whose topology is used in different fields such as computer science, combinatorics, code theory, etc. Thus, the study of spanning of graphs in the hypercube has received much interest these later years. The problem consist of giving the smallest dimension of a hypercube in which a given graph is embeddable. We talk then about optimal hypercube and cubical dimension of the graph. Arfati et al. [1] have proved that the problem of deciding if a graph is embeddable in a hypercube of a given dimension is NP-complete, Corneil and Wagner [2] have shown that this problem is NP-complete even in the case where G is a tree. In this paper, we introduce two new classes of balanced binary trees for which the cubical dimension is given.

Mots clés

Hypercubes,Trees, Embedding, Isomorphism.

Les articles similaires

L’adaptation Du Balanced Scorecard à L’établissement Hospitalier Spécialisé Public En Algérie Adaptation Of The Balanced Scorecard To The Specialized Hospital Establishment In Algeria

Dr. Dahak Nadjia . 
pages 475-486.

The Role Of Teachers In Embedding Culture Within The New Learnt Language In The Translation Subject-matter: A Case Study Of Second Year Students Of English

Sekhri Ouided . 
pages 65-75.

Plongement Et Placement De Certaines Classes D’arbres Dans L’hypercube

Kabyl Kamal .  Berrachedi Abdelhafid . 
pages 21-24.

Plongement Optimal D’arbres Binaires équilibrés Dans L’hypercube

Kabyl Kamal .  Berrachedi Abdelhafid . 
pages 19-22.

Automatic And Semi-automatic Counting Of Palm Trees From Remote Sensing Images With Very High Spatial Resolution

Kherroub Khoudir .  Hong Shu . 
pages 54-64.

Formats de citation