LINEAR RECOGNITION ALGORITHM FOR COGRAPHS.

D. G. Corneil, Y. Perl, L. K. Stewart

Research output: Contribution to journalArticlepeer-review

434 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)926-934
Number of pages9
JournalSIAM Journal on Computing
Volume14
Issue number4
DOIs
StatePublished - Jan 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'LINEAR RECOGNITION ALGORITHM FOR COGRAPHS.'. Together they form a unique fingerprint.

Cite this