A Note on Finding all Homogeneous Set Sandwiches

Abstract : A homogeneous set is a set of vertices H of a graph G=(V,E) such that each vertex of V\H is either adjacent to all vertices of H or none of them. A graph Gs=(V,Es) is a sandwich for a pair of graph Gt=(V,Et) and G=(V,E) if Es is included in E and contains Et. In a recent paper of Tang et al, a polynomial algorithm is described for computing all the possible homogeneous sets for the sandwich graphs of Gt and G. In this paper, we invalidate this algorithm by proving there are exponentially many such sets. We give a correct characterization of a homogeneous set of a sandwich graph.
Type de document :
Rapport
02141, 2002, pp.7
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090365
Contributeur : Christine Carvalho de Matos <>
Soumis le : mercredi 30 août 2006 - 11:59:29
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:42:23

Fichier

Identifiants

  • HAL Id : lirmm-00090365, version 1

Collections

Citation

Michel Habib, Emmanuelle Lebhar, Christophe Paul. A Note on Finding all Homogeneous Set Sandwiches. 02141, 2002, pp.7. 〈lirmm-00090365〉

Partager

Métriques

Consultations de la notice

185

Téléchargements de fichiers

158