Algorithmic Aspects of a General Modular Decomposition Theory
Binh-Minh Bui-Xuan, Michel Habib, Vincent Limouzy, Fabien de Montgolfier · 2006
Abstract. This paper introduces the ulmods, a generalisation of modules for the homogeneous relations. We first present some properties of the ulmod family, then show that, if the homogeneous relation fulfills some natural axioms, the ulmod family has a unique decomposition tree. Under a certain size assumption we show that this tree can be computed in polynomial time. We apply this theory to a new tournament decomposition and a graph decomposition. In both cases, the polynomial decomposition tree computing time becomes linear. Moreover, we characterise completely decomposable relations and give necessary and sufficient condition for testing if a given homogeneous relation corresponds to a graph or to a tournament, with a polynomial-time test. Finally we give polynomial-time algorithms for the maximal ulmods and the undecomposability of a relation, and conclude with further applications of homogeneous relations. 1