Skip to Main content Skip to Navigation
Reports

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.
Document type :
Reports
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090365
Contributor : Christine Carvalho de Matos <>
Submitted on : Wednesday, August 30, 2006 - 11:59:29 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:42:23 AM

File

Identifiers

  • 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⟩

Share

Metrics

Record views

255

Files downloads

239