Incremental modular decomposition

Abstract

Modular decomposition is a form of graph decomposition that has been discovered independently by researchers in graph theory, game theory, network theory, and other areas. This paper reduces the time needed to find the modular decomposition of a graph from Ω( n 3 ) to Ο( n 2 ). Together with a new algorithm for transitive orientation given in [21], this leads to fast new algorithms for a number of problems in graph recognition and isomorphism, including recognition of comparability graphs and permutation graphs. The new algorithm works by inserting each vertex successively into the decomposition tree, using Ο( n ) time to insert each vertex.