A Simple Paradigm for Graph Recognition : Application to Cographs and Distance Hereditary Graphs

Abstract : An easy way for graph recognition algorithms is to use a two-step process: first, compute a characteristic feature as if the graph belongs to that class; second, check whether the computed feature really defines the input graph. Although in some cases the two steps can be merged, separating them may yield new and much more easily understood algorithms. In this paper we apply that paradigm to the cograph and distance hereditary graph recognition problems.
keyword : GRAPH
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2001, 263 (1-2), pp.99-111
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090372
Contributeur : Christine Carvalho de Matos <>
Soumis le : mercredi 30 août 2006 - 12:10:27
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:42:46

Fichier

Identifiants

  • HAL Id : lirmm-00090372, version 1

Collections

Citation

G. Damiand, Michel Habib, Christophe Paul. A Simple Paradigm for Graph Recognition : Application to Cographs and Distance Hereditary Graphs. Theoretical Computer Science, Elsevier, 2001, 263 (1-2), pp.99-111. 〈lirmm-00090372〉

Partager

Métriques

Consultations de la notice

287

Téléchargements de fichiers

268