A Simple Linear Time LexBFS Cograph Recognition Algorithm
Abstract
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.
Domains
Computer Science [cs]![]()
Is described by lirmm-00324572 Journal article Anna Bretscher, Derek Corneil, Michel Habib, Christophe Paul. A Simple Linear Time LexBFS Cograph Recongition Algorithm. SIAM Journal on Discrete Mathematics, 2008, 22 (4), pp.1277-1296. ⟨10.1137/060664690⟩. ⟨lirmm-00324572⟩