%0 Journal Article
%T Algorithms for Dominating Set Problems in OTIS Networks
OTIS网络的支配集问题算法研究
%A 向永香
%A 叶慧
%A 李旻
%A 陈卫东
%J 计算机科学
%D 2012
%I
%X 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.
%K Network
%K OTIS network
%K Graph
%K Dominating set
%K Connected dominating set
%K Algorithm
网络,OTIS网络,图,支配集,连通支配集,算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=64488958E8AA8ED354A923B5D846B38B&yid=99E9153A83D4CB11&vid=7C3A4C1EE6A45749&iid=38B194292C032A66&sid=39EEF47180459690&eid=C3BF5C58156BEDF0&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=0