Linear recognition of generalized Fibonacci cubes $Q_h(111)$

Abstract : The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 \ldots b_h$ containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.349-362
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01364442
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 12 septembre 2016 - 15:50:59
Dernière modification le : jeudi 7 septembre 2017 - 01:03:45
Document(s) archivé(s) le : mardi 13 décembre 2016 - 15:23:17

Fichier

2756-9997-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01364442, version 1

Collections

Citation

Yoomi Rho, Aleksander Vesel. Linear recognition of generalized Fibonacci cubes $Q_h(111)$. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.349-362. 〈hal-01364442〉

Partager

Métriques

Consultations de la notice

40

Téléchargements de fichiers

302