A Simple Linear Time LexBFS Cograph Recognition Algorithm

2008/01/01 by Anna Bretscher, Derek G. Corneil, Michel Habib +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Algorithms and Data Compression #Lexicographical order #Algorithm #Simple (philosophy) #Mathematics #Cograph #Time complexity #Combinatorics #Graph #Modular design #Computer science #Theoretical computer science #Pathwidth #Line graph

paper · doi:10.1137/060664690

openalex publication_date 2008/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07

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₄-reducible, P₄-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.

Citations

• A Linear Recognition Algorithm for Cographs
• Complement reducible graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A simple linear time algorithm for cograph recognition

Cited by

• The LBFS Structure and Recognition of Interval Graphs
• Cograph [wikipedia]

Related

• Linear Time LexDFS on Cocomparability Graphs
• (Quasi-)linear time algorithm to compute LexDFS, LexUP and LexDown orderings
• Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition
• A recursive linear time modular decomposition algorithm via LexBFS
• The LBFS Structure and Recognition of Interval Graphs