Modular decomposition of k-hypergraphs

Abstract

A module is a subset of vertices in a graph wherein each vertex outside the module is either adjacent to all or none of the vertices inside it. The modular decomposition tree of a graph gives an O(n)-space representation of the modules in a graph. The notion of modules in graphs has been extended to hypergraphs by Bonizzoni and Della Vedova [6]. Bonizzoni and Della Vedova also provide an algorithm to compute the decomposition tree with a time-bound of O(n3k–5), where k is the maximum size of hyperedges in the hypergraph. In this thesis, I provide a new time-bound to compute the decomposition tree in hypergraphs of O(k!nk–2m log n), where m is the number of edges. The new algorithm takes advantage of sparseness in the hypergraph. Even in dense hypergraph, where there are O(nk) edges, the new time-bound is O(k!n2k–2 log n) which is still better than O(n3k–5) for k greater than or equal to four.