Recognizing cographs and threshold graphs through a classification of their edges
In this work, we attempt to establish recognition properties and characterization for two classes of perfect graphs, namely cographs and threshold graphs, leading to constant-time parallel recognition algorithms. We classify the edges of an undirected graph as either free, semi-free or actual, and define the class of A-free graphs as the class containing all the graphs with no actual edges. Then, we define the actual subgraph G(a) of a non-A-free graph G as the subgraph containing all the actual edges of G. We show properties and characterizations for the class of A-free graphs and the actual subgraph G(a) of a cograph G, and use them to derive structural and recognition properties for cographs and threshold graphs. These properties imply parallel recognition algorithms which run in O(1) time using O(nm) processors. (C) 2000 Elsevier Science B.V. All rights reserved.
cographs threshold graphs recognition edge classification graph partition parallel algorithms complexity