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].

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