Abstract: The minimum dominating set problem and the minimum connected dominating set problem, both of which are NP-hard problems, have many important applications in the fields related to networks and parallel&distributed computing. Recent OhIS networks arc a class of two-levcl structure interconnection networks taking any graph as modules and connecting them in a complete graph manner, which provides a systematic competitive construction scheme for large,scalable, modular, and robust parallel architectures while maintaining favorable properties of their factor networks. In this paper, how to construct a small dominating set and connected dominating set of an OhIS network was discussed. Based on the connectivity rule of OTIS networks,we gave algorithms for constructing a small dominating set (a small connected dominating set, respectively) of an O`hIS network from a dominating set (a connected dominating set, respeclively) of its factor network. The performances of these algorithms were analyzed, and were shown by examples.

Key words: Network, OTIS network, Graph, Dominating set, Connected dominating set, Algorithm