A fully dynamic algorithm for modular decomposition and recognition of cographs

✍ Scribed by Ron Shamir; Roded Sharan

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 236 KB
• Volume: 136
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00448-7

✦ Synopsis

The problem of dynamically recognizing a graph property calls for e ciently deciding if an input graph satisÿes the property under repeated modiÿcations to its set of vertices and edges. The input to the problem consists of a series of modiÿcations to be performed on the graph. The objective is to maintain a representation of the graph as long as the property holds, and to detect when it ceases to hold. In this paper, we solve the dynamic recognition problem for the class of cographs and some of its subclasses. Our approach is based on maintaining the modular decomposition tree of the dynamic graph, and using this tree for the recognition. We give the ÿrst fully dynamic algorithm for maintaining the modular decomposition tree of a cograph. We thereby obtain fully dynamic algorithms for the recognition of cographs, threshold graphs, and trivially perfect graphs. All these algorithms work in constant time per edge modiÿcation and O(d) time per d-degree vertex modiÿcation.