# A Simple Linear Time LexBFS Cograph Recongition Algorithm

3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Recently Lexicographic Breadth First Search (LexBFS) has been shown to be a very powerful tool for the development of linear time, easily implementable recognition algorithms for various families of graphs. In this paper, we add to this work by producing a simple two LexBFS sweep algorithm to recognize the family of cographs. This algorithm extends to other related graph families such as $P_4$-reducible, $P_4$-sparse and distance hereditary. It is an open question whether our cograph recognition algorithm can be extended to a similarly easy algorithm for modular decomposition.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2008, 22 (4), pp.1277-1296

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324572
Contributeur : Christophe Paul <>
Soumis le : jeudi 25 septembre 2008 - 14:23:55
Dernière modification le : jeudi 15 novembre 2018 - 20:26:55

### Identifiants

• HAL Id : lirmm-00324572, version 1

### Citation

Anna Bretscher, Derek Corneil, Michel Habib, Christophe Paul. A Simple Linear Time LexBFS Cograph Recongition Algorithm. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2008, 22 (4), pp.1277-1296. 〈lirmm-00324572〉

### Métriques

Consultations de la notice