Modular decomposition of k-hypergraphs

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(n 3k-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.{09}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.