报告名称：几何交图控制问题的相关算法

报告专家：徐守军

专家所在单位：兰州大学

报告时间：2024年6月15日10:00-11:00

报告地点: 永利集团88304官网204会议室

专家简介：徐守军，现为兰州大学数学与统计学院教授，博士生导师。2007年取得理学博士学位, 导师张和平教授。博士毕业后在中科院数学与系统科学研究院从事为期两年的博士后研究。2010.2-2011.2与2016.9-2017.9，在美国加州大学戴维斯分校计算机系访问两年，合作者为世界著名计算生物学家Dan Gusfield教授；2013年6月至9月、2015年12月至2016年1月，在香港教育学院访问。担任中国运筹学会理事，中国工业与应用数学学会图论组合及应用常务委员，中国运筹学会图论组合学分会理事，美国数学会《数学评论》评论员，图论，组合优化，离散数学，计算机算法等领域期刊的审稿人。近五年主要承担了6项科研项目，其中国家自然科学基金面上项目3项，军工类项目2项，重庆市自然科学基金创新发展联合基金 (重点项目) 1项，累计经费257万元。目前在SIAM J Discrete Math.，J. Graph Theory，Discrete Math.，Inform.Process.Lett.，Discrete Appl.Math，Theor. Comput.Sci. J.Combin.Optim.，Int.J.Quantum Chem，MATCH等重要期刊上发表论文50余篇。

报告摘要：本报告研究了在几何交图中的3个最小控制问题:total (MTDS)， total constrained (MTRDS)和secure (MSDS)问题。首先，证明了这三个问题的决策版本在网格图(单位盘图和单位方交图的一个子类)中是NP-完全的，强化了Jena等人在2021年关于单位盘图的MTDS问题的结果。进一步证明了矩形交图中的MSDS问题是APX-困难的。其次，我们给出了三个问题的线性时间常数逼近算法。最后，我们针对单位圆盘图和单位平方图中的MTRDS问题和MSDS问题提出了PTASs算法。