报告题目：几种几何交叉图中的支配问题算法

报告时间：2024年11月4日（星期一）14:00--16:00

报告地点：理学院B315

主办单位：理学院

报告人：徐守军

报告人简介：

徐守军,兰州大学教授、博士生导师，数学与统计学院副院长。现任中国运筹学会图论组合学分会第四届理事会青年理事， 中国工业与应用数学学会图论组合及应用专业委员会委员。 主要研究领域为图论及组合最优化、计算机算法及离散数学等。在SIAM J Discrete Math， Discrete Appl. Math, J. Combin. Optim.，Int. J. Quantum Chem, MATCH, Australas. J. Combin.等国际期刊上发表论文四十余篇。 2012年，获得甘肃省自然科学奖三等奖； 2013年，获得甘肃省高等学校青年教师成才奖；2015年，获兰州大学隆基教学骨干奖。主持完成国家自然科学基金项目3项。

报告内容简介：

研究三种最小支配问题：全支配问题(MTDS)、全限制支配问题 (MTRDS) 和安全支配问题 (MSDS) 在几何交叉图中的算法性质。首先，证明了这三个问题的判定版本在网格图（一类单位圆图和单位方形交叉图的子类）中是NP完全的，这加强了Jena等人在2021年关于单位圆图中MTDS问题的结果。进一步地，证明MSDS问题在矩形交叉图中是APX困难的。其次，给出了一些在单位圆图中针对这三个问题的线性时间常数近似算法。最后，为单位圆图和单位方形图中的MTRDS问题和MSDS问题提出了全局逼近方案 (PTAS)。