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.
No takes yet. Share an insight, caveat, or question.
Bretscher et al. (2008) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: