澳门葡京赌场官网-金沙赌场注册送体验金

報告題目：幾種幾何交叉圖中的支配問題算法

報告時間：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)。