Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0575.68065
Corneil, D.G.; Perl, Y.; Stewart, L.K.
A linear recognition algorithm for cographs. (English)
[J] SIAM J. Comput. 14, 926-934 (1985). ISSN 0097-5397; ISSN 1095-7111/e

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.

MSC 2000:: *68R10 Graph theory in connection with computer science

Keywords: permutation graphs; perfect graphs; examination scheduling; automatic clustering of index terms; cotree; chromatic number; clique determination; minimum weight domination; isomorphism; minimum fill-in; Hamiltonicity; linear time algorithm

Cited in: Zbl 1099.68680 Zbl 0827.05056 Zbl 0953.05506

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]