zbMATH — the first resource for mathematics

A simple linear time LexBFS cograph recognition algorithm. (English) Zbl 1255.68108
Bodlaender, Hans L. (ed.), Graph-theoretic concepts in computer science. 29th international workshop, WG 2003, Elspeet, The Netherlands, June 19–21, 2003. Revised papers. Berlin: Springer (ISBN 3-540-20452-0/pbk). Lect. Notes Comput. Sci. 2880, 119-130 (2003).
Summary: This paper introduces a new simple linear time algorithm to recognize cographs (graphs without an induced $$P _{4})$$. Unlike other cograph recognition algorithms, the new algorithm uses a multisweep Lexicographic Breadth First Search (LexBFS) approach, and introduces a new variant of LexBFS, called LexBFS$$^{-}$$, operating on the complement of the given graph $$G$$ and breaking ties with respect to an initial LexBFS. The algorithm either produces the cotree of $$G$$ or identifies an induced $$P _{4}$$.
For the entire collection see [Zbl 1029.00043].

MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects)
Full Text: