Skip to Main content Skip to Navigation
Journal articles

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
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00090372
Contributor : Christine Carvalho de Matos <>
Submitted on : Wednesday, August 30, 2006 - 12:10:27 PM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:42:46 AM

File

Identifiers

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. ⟨10.1016/S0304-3975(00)00234-6⟩. ⟨lirmm-00090372⟩

Share

Metrics

Record views

718

Files downloads

656