澳门永利赌场龙-澳门永利赌场现况-网上赌博网址

報(bào)告題目：幾種幾何交叉圖中的支配問(wèn)題算法

報(bào)告時(shí)間：2024年11月4日（星期一）14:00--16:00

報(bào)告地點(diǎn)：理學(xué)院B315

主辦單位：理學(xué)院

報(bào)告人：徐守軍

報(bào)告人簡(jiǎn)介：

徐守軍,蘭州大學(xué)教授、博士生導(dǎo)師，數(shù)學(xué)與統(tǒng)計(jì)學(xué)院副院長(zhǎng)?，F(xiàn)任中國(guó)運(yùn)籌學(xué)會(huì)圖論組合學(xué)分會(huì)第四屆理事會(huì)青年理事， 中國(guó)工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會(huì)圖論組合及應(yīng)用專(zhuān)業(yè)委員會(huì)委員。 主要研究領(lǐng)域?yàn)閳D論及組合最優(yōu)化、計(jì)算機(jī)算法及離散數(shù)學(xué)等。在SIAM J Discrete Math， Discrete Appl. Math, J. Combin. Optim.，Int. J. Quantum Chem, MATCH, Australas. J. Combin.等國(guó)際期刊上發(fā)表論文四十余篇。 2012年，獲得甘肅省自然科學(xué)獎(jiǎng)三等獎(jiǎng)； 2013年，獲得甘肅省高等學(xué)校青年教師成才獎(jiǎng)；2015年，獲蘭州大學(xué)隆基教學(xué)骨干獎(jiǎng)。主持完成國(guó)家自然科學(xué)基金項(xiàng)目3項(xiàng)。

報(bào)告內(nèi)容簡(jiǎn)介：

研究三種最小支配問(wèn)題：全支配問(wèn)題(MTDS)、全限制支配問(wèn)題 (MTRDS) 和安全支配問(wèn)題 (MSDS) 在幾何交叉圖中的算法性質(zhì)。首先，證明了這三個(gè)問(wèn)題的判定版本在網(wǎng)格圖（一類(lèi)單位圓圖和單位方形交叉圖的子類(lèi)）中是NP完全的，這加強(qiáng)了Jena等人在2021年關(guān)于單位圓圖中MTDS問(wèn)題的結(jié)果。進(jìn)一步地，證明MSDS問(wèn)題在矩形交叉圖中是APX困難的。其次，給出了一些在單位圓圖中針對(duì)這三個(gè)問(wèn)題的線(xiàn)性時(shí)間常數(shù)近似算法。最后，為單位圓圖和單位方形圖中的MTRDS問(wèn)題和MSDS問(wèn)題提出了全局逼近方案 (PTAS)。