Approximation Algorithm for the Fault-Tolerant Connected Dominating Set Problem
发布人: 曹思圆   发布时间: 2022-05-11   浏览次数: 10

*时间:20220513日 1500-1600

*地点:腾讯会议: 601-176-918

*主讲人:张昭 教授

*主持人:吕长虹 教授


Approximation algorithm deals with NP-hard problems by providing theoretically guaranteed accuracy analysis. In this talk, I’ll present some of our approximation algorithms for the construction of fault-tolerant virtual backbone of a wireless sensor network, which can be modeled as a (k,m)-connected dominating set in a graph. The focus will be put on the methods and developing ideas for the design and analysis.