A Simple Linear Time LexBFS Cograph Recongition Algorithm - Archive ouverte HAL Access content directly
Journal Articles SIAM Journal on Discrete Mathematics Year : 2008

A Simple Linear Time LexBFS Cograph Recongition Algorithm

(1) , (1) , (2) , (3)
1
2
3
Anna Bretscher
• Function : Author
Derek Corneil
• Function : Author
Michel Habib
Christophe Paul

Abstract

Recently Lexicographic Breadth First Search (LexBFS) has been shown to be a very powerful tool for the development of linear time, easily implementable recognition algorithms for various families of graphs. In this paper, we add to this work by producing a simple two LexBFS sweep algorithm to recognize the family of cographs. This algorithm extends to other related graph families such as $P_4$-reducible, $P_4$-sparse and distance hereditary. It is an open question whether our cograph recognition algorithm can be extended to a similarly easy algorithm for modular decomposition.

Dates and versions

lirmm-00324572 , version 1 (25-09-2008)

Identifiers

• HAL Id : lirmm-00324572 , version 1
• DOI :

Cite

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⟩

194 View