学术动态

学术动态

学术活动

当前您的位置: 网站首页 - 学术动态 - 学术活动 - 正文

讲座题目:Approximating the minimum independent dominating set - Smoothed analysis

作者: 编辑: 发布时间:2013-06-09

报告人: 林国辉教授 加拿大Alberta大学


时  间: 2013年6月13日(星期四)上午10:00~11:30

地  点: 西安交通大学管理学院313教室


讲座内容:


We investigate the minimum independent dominating set in perturbed graphs, obtained by negating the existence of edges independently with a probability. We prove the asymptotic value of the size of the minimum independent dominating set and present a simple greedy algorithm for this problem and with polynomial expected running time.


林国辉教授简介:


1998年于中科院应用数学所获得博士学位,1998-2001年先后在佛蒙特大学、加拿大滑铁卢大学和麦克马斯特大学从事博士后研究,现任加拿大阿尔伯特大学计算科学系教授。林国辉教授主要研究兴趣包括优化算法设计与分析,机器学习,数据库和数据发掘和生物信息学和计算生物学。