15015.最小權(quán)和的連通頂點(diǎn)p3覆蓋問(wèn)題

1、學(xué)位論文獨(dú)創(chuàng)性聲明本人鄭重聲明：所提交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作和取得的研究成果本論文中除引文外，所有實(shí)驗(yàn)、數(shù)據(jù)和有關(guān)材料均是真實(shí)的本論文中除引文和致謝的內(nèi)容外，不包含其他人或其它機(jī)構(gòu)已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果其他同志對(duì)本研究所做的貢獻(xiàn)均己在論文中作了聲明并表示了謝意學(xué)位論文作者簽名：王示1民學(xué)位論文使用授權(quán)聲明研究生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位屬南京師范大學(xué)學(xué)校有權(quán)保存本學(xué)位論文的電子和紙質(zhì)文檔，可以借閱或上

2、網(wǎng)公布本學(xué)位論文的部分或全部?jī)?nèi)容，可以采用影印、復(fù)印等手段保存、匯編本學(xué)位論文學(xué)校可以向國(guó)家有關(guān)機(jī)關(guān)或機(jī)構(gòu)送交論文的電子和紙質(zhì)文檔，允許論文被查閱和借閱(保密論文在解密后遵守此規(guī)定)保密論文注釋?zhuān)罕緦W(xué)位論文屬于保密論文，密級(jí)：保密期限為學(xué)位論文作者簽名：王烈瓦13期：硎蜱櫥陽(yáng)指導(dǎo)教師簽名：弘曉芝日期：矽答軍鉚力日ContentsAbstract(inChinese)，。。。，。，，，。。，。。。。。。。，。。mAbstract(inEn

3、glish)、，ChapterlIntroduction111Basicdefinition112ThebackgroundandsomeknownresultsofvertexcoverRproblem313功emethodsandmainresults4Chapter2PTASfortheMWCVCP3problemonunitdiskgraphs621AnoutlineoftheapproachandNP—hardness622A

4、pproximationresultandthePTASalgorithm1023AnalysisofthePTASalgorithm12231TheCOlTg圮trlessofthealgorithm12232Timecomplexity13233Performanceanalysis15Chapter3PTASfortheMWCVCP3problemonunitballgraphsl931Partitionandshiftingst