报告题目:几种几何交叉图中的支配问题算法
报告时间: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)。