37000gcom威尼斯2024第 17期 数理大讲堂

主讲人：徐守军 教授

主持人：高利新 教授

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

讲座地点：37000gcom威尼斯南校区37000gcom威尼斯3B301

讲座题目：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.等杂志上。