A Note on Finding all Homogeneous Set Sandwiches - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2002

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.

Domains

Other [cs.OH]
Fichier principal
Vignette du fichier
D17.PDF (186.27 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00090365 , version 1 (30-08-2006)

Identifiers

  • HAL Id : lirmm-00090365 , version 1

Cite

Michel Habib, Emmanuelle Lebhar, Christophe Paul. A Note on Finding all Homogeneous Set Sandwiches. 02141, 2002, pp.7. ⟨lirmm-00090365⟩
146 View
348 Download

Share

Gmail Facebook X LinkedIn More