A linear recognition algorithm for cographs

Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination sched...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1985-11, Vol.14 (4), p.926-934
Main Authors: CORNEIL, D. G, PERL, Y, STEWART, L. K
Format: Article
Language:English
Subjects:
Algorithms
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Graphs
Heuristic
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms. Furthermore, it is known that cographs have a unique tree representation called a cotree. Using the cotree it is possible to design very fast polynomial time algorithms for problems which are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in and Hamiltonicity. In this paper we present a linear time algorithm for recognizing cographs and constructing their cotree representation.
ISSN:0097-5397
1095-7111
DOI:10.1137/0214065