Skip to Main content Skip to Navigation
Journal articles

A Simple Linear Time LexBFS Cograph Recongition Algorithm

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.
Document type :
Journal articles
Complete list of metadatas
Contributor : Christophe Paul <>
Submitted on : Thursday, September 25, 2008 - 2:23:55 PM
Last modification on : Friday, March 27, 2020 - 3:43:32 AM


  • HAL Id : lirmm-00324572, version 1



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⟩



Record views