A Simple Linear Time LexBFS Cograph Recognition Algorithm - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2003

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.

Dates and versions

lirmm-00269525 , version 1 (03-04-2008)

Identifiers

Cite

Anna Bretscher, Derek Corneil, Michel Habib, Christophe Paul. A Simple Linear Time LexBFS Cograph Recognition Algorithm. WG 2003 - 29th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2003, Elspeet, Netherlands. pp.119-130, ⟨10.1007/978-3-540-39890-5_11⟩. ⟨lirmm-00269525⟩
123 View
0 Download

Altmetric

Share

More