A SIMPLE LINEAR TIME LexBFS COGRAPH RECOGNITION ALGORITHM

被引：31

作者：

Bretscher, Anna ^{[1
]}

Corneil, Derek ^{[1
]}

Habib, Michel ^{[2
]}

Paul, Christophe ^{[3
]}

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 2GA, Canada

[2] Univ Paris 07, CNRS, LIAFA, F-75251 Paris 05, France

[3] Univ Montpellier 2, CNRS, LIRMM, F-34392 Montpellier 5, France

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2008年 / 22卷 / 04期

关键词：

graph algorithms; cograph recognition; linear time algorithms; LexBFS; P-4-free graphs; modular decomposition;

D O I：

10.1137/060664690

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1277 / 1296

页数：20

共 28 条

[1] LexBFS-orderings and powers of chordal graphs [J].

Brandstadt, A ;

Dragan, FF ;

Nicolai, F .

DISCRETE MATHEMATICS, 1997, 171 (1-3) :27-42

[2]

BRANDSTADT A, 1999, SIAM MONOGR DISCRETE, V3

[3]

Bretscher A, 2003, LECT NOTES COMPUT SC, V2880, P119

[4]

BRETSCHER A, 2004, THESIS U TORONTO TOR

[5]

Chang JM, 2000, LECT NOTES COMPUT SC, V1741, P163

[6]

Corneil D.G., 1998, Symposium on Discrete Algorithms, P175

[7] A UNIFIED VIEW OF GRAPH SEARCHING [J].

Corneil, Derek G. ;

Krueger, Richard M. .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (04) :1259-1276

[8]

Corneil DG, 2004, LECT NOTES COMPUT SC, V3353, P1

[9] COMPLEMENT REDUCIBLE GRAPHS [J].

CORNEIL, DG ;

LERCHS, H ;

BURLINGHAM, LS .

DISCRETE APPLIED MATHEMATICS, 1981, 3 (03) :163-174

[10] A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs [J].

Corneil, DG .

DISCRETE APPLIED MATHEMATICS, 2004, 138 (03) :371-379

← 1 2 3 →