%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