报告地点：行健楼665
邀请人：张晓岩教授
摘要：Let G = (V; E) be a graph and m be a positive integer less than or equal to the minimum degree of G. By an m-fold outer-connected dominating set (m-fold OCDS ) of G, we meana subset C in V such that every vertex in V\C has at least m neighbors in C and the subgraph of G induced by V\C is connected. In this talk, we present a greedy algorithm to compute an m-fold OCDS in general graphs and give approximation ratio of the minimum m-fold OCDS. This is a joint work with Xiaozhi Wang, Xianyue Li, Bo Hou, Wen Liu and Lidong Wu.
