您当前的位置: 首页 信息中心 教工公告 正文

教工公告

2024年5月10日徐守军教授学术讲座

来源:新葡萄8883官网AMG 浏览人数: 发布时间:2024-05-08

新葡萄8883官网AMG2024第 17期 数理大讲堂

主讲人:徐守军 教授

主持人:高利新 教授

讲座时间:2024年5月10日16:30-17:00

讲座地点:新葡萄8883官网AMG南校区新葡萄8883官网AMG3B301

讲座题目:Algorithmic aspects of domination problems in Geometric Intersection Graphs

摘要:We consider 3 minimum dominating problems: total (MTDS), total restrained (MTRDS) and secure (MSDS) in geometric intersection graphs. Firstly, we show that the decision version of the three problems are NP-complete in grid graphs (a subclass of unit disk graphs and unit square intersection graphs),strengthening the result on the MTDS problem in unit disk graphs by Jena et al. in 2021. Further we show that the MSDS problem is APX-hard in rectangle intersection graphs. Secondly, we give some linear-time constant-approximation algorithms for the three problems in unit disk graphs. Finally, we propose PTASs for the MTRDS problem and the MSDS problem in unit disk graphs and unit square graphs.

个人简介:

徐守军, 兰州大学数学与统计学院教授, 博士生导师。2007年获得兰州大学博士学位. 2008-2010,中科院数学与系统科学研究院从事运筹学方向博士后工作. 研究方向主要是图论及其应用, 学术论文主要发表在J Graph theroy, SIAM J Discrete Math,Discrete Math. Discrete Appl.Math., Theor. Comput. Sci., Inform., Process. Lett., J. Combin. Optim.,Australas. J. Combin.等杂志上。

联系我们

地址:新葡萄8883官网AMG南校区3号楼 电话:00-86-0577-86689098 传真:00-86-0577-86689528 邮编:325035 邮箱:slxy@wzu.edu.cn

关注我们

版权所有

新葡萄8883·(AMG认证)官方网站-Delight the World 浙ICP备07006821号-1 技术支持:捷点科技