A Simple Paradigm for Graph Recognition : Application to Cographs and Distance Hereditary Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2001

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

Résumé

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.

Mots clés

Fichier principal
Vignette du fichier
D21.PDF (174.96 Ko) Télécharger le fichier

Dates et versions

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

Identifiants

Citer

Guillaume Damiand, Michel Habib, Christophe Paul. A Simple Paradigm for Graph Recognition : Application to Cographs and Distance Hereditary Graphs. Theoretical Computer Science, 2001, 263 (1-2), pp.99-111. ⟨10.1016/S0304-3975(00)00234-6⟩. ⟨lirmm-00090372⟩
324 Consultations
860 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More