A greedy algorithm for the m-fold OCDS problem
报告人:高锁刚教授,河北师范大学 时间:2019年11月11日(周一)9:00
报告地点:行健楼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.