A Simple Linear Time LexBFS Cograph Recognition Algorithm

Anna Bretscher 1 Derek Corneil 1 Michel Habib 2 Christophe Paul 3
1 DCS - Department of Computer Science [University of Toronto]
2 LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper introduces a new simple linear time algorithm to recognize cographs (graphs without an induced P 4). Unlike other cograph recognition algorithms, the new algorithm uses a multisweep Lexicographic Breadth First Search (LexBFS) approach, and introduces a new variant of LexBFS, called LexBFS−, operating on the complement of the given graph G and breaking ties with respect to an initial LexBFS. The algorithm either produces the cotree of G or identifies an induced P 4.
Type de document :
Communication dans un congrès
H. Bodleander. WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2003, Elspeet, Netherlands. 29th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (2880), pp.119-130, 2003, Graph-Theoretic Concepts in Computer Science. 〈10.1007/978-3-540-39890-5_11〉
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269525
Contributeur : Christine Carvalho de Matos <>
Soumis le : jeudi 3 avril 2008 - 08:21:42
Dernière modification le : mercredi 10 octobre 2018 - 21:28:02

Lien texte intégral

openaccess

Identifiants

Collections

ALGCO | LIRMM | MIPS | UNIV-MONTPELLIER

Relations

Citation

Anna Bretscher, Derek Corneil, Michel Habib, Christophe Paul. A Simple Linear Time LexBFS Cograph Recognition Algorithm. H. Bodleander. WG: Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2003, Elspeet, Netherlands. 29th International Workshop on Graph-Theoretic Concepts in Computer Science, LNCS (2880), pp.119-130, 2003, Graph-Theoretic Concepts in Computer Science. 〈10.1007/978-3-540-39890-5_11〉. 〈lirmm-00269525〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

82

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD