Back to Search
Start Over
A simple linear time algorithm for cograph recognition
- Source :
-
Discrete Applied Mathematics . Jan2005, Vol. 145 Issue 2, p183-197. 15p. - Publication Year :
- 2005
-
Abstract
- Abstract: In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the -free graphs (where 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. [Copyright &y& Elsevier]
- Subjects :
- *ALGORITHMS
*PERMUTATIONS
*GRAPH theory
*ALGEBRA
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 145
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 19275179
- Full Text :
- https://doi.org/10.1016/j.dam.2004.01.011