Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328491 | Discrete Applied Mathematics | 2005 | 15 Pages |
Abstract
In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the P4-free graphs (where P4 denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michel Habib, Christophe Paul,