資源描述：
《s--路徑頂點(diǎn)覆蓋問(wèn)題的算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、14文章組織結(jié)構(gòu)6第二章?tīng)?zhēng)路徑頂點(diǎn)覆蓋問(wèn)題的研宄72l}路徑頂點(diǎn)覆蓋問(wèn)題721ls．路徑頂點(diǎn)覆蓋問(wèn)題的復(fù)雜性72,2樹(shù)上的爭(zhēng)路徑頂點(diǎn)覆蓋問(wèn)題的擐優(yōu)算法82,3本章小結(jié)9第三章3．路徑頂點(diǎn)覆蓋問(wèn)題的算法研究103I3-路徑頂點(diǎn)覆蓋10323．路徑頂點(diǎn)覆蓋問(wèn)題的一個(gè)最優(yōu)算法lo3．33-路徑頂點(diǎn)覆蓋問(wèn)題算法的改進(jìn)13331算法的第一次改進(jìn)13332算法的第二次改進(jìn)153．33算法的第三次改進(jìn)??15334算法的第四次改進(jìn)173．35算法的第五次政進(jìn)?1934本章小結(jié)?24第四章4．路徑頂點(diǎn)覆蓋問(wèn)題的算法研究264I4-路徑頂點(diǎn)覆蓋26424-路徑頂點(diǎn)覆蓋問(wèn)題的一個(gè)最優(yōu)算
2、法?27434-路徑頂點(diǎn)覆蓋問(wèn)題算法的改進(jìn)3l431算法的第一次改進(jìn)3l山東大學(xué)碩士學(xué)位論文生塹奎蘭堡圭蘭堡絲苧CONTENTSAbstractInChineseIAbnrminEn目ish11ChapterOneIntroduction?llApplicationBackwood12ResearchStatus2L3PararneterizedAlgorithm3l31D∞thBoundedSearchTree3l4ThesisStractum6ChapterTwoResearchons-PathVen靠CoverProblem721s-PathVer嗽Cover
3、Problem72llTheComplexityofs-PathVertexCoverProblem72．2An0pnmmalgorithmforthes-PathVeftexCoverProbleminTrees823Summary9ChapterThreeResearchoriAlgorithemsforthe3-PathVenexCoverProblem10313-PathVcne，【CoverlO32An0DnrrIalAlgorithmforthe3-PathVertexCoverProblemIO33TheImprovementoftheAlgorith
4、mofthe3-pathVertexCoverProblem1331TheFirstImprovement133．32TheSecondImprovement153TheThirdImprovement1534TheFourthImprovement1735TheFifthImprovement193．4Summary24ChapterFourResearchonAlgorithemsforthe4-PathVertexCoverProblem264I4．PathVertexCover264．2AnOptimalAlgorithmforme4-PathVertexC
5、overProblem2743TheImprovementoftheAlgorithmofthe4-PathVertexCoverProblem31431TheFirstImprovement3l432TheSecondImprovement?，3433TheThlrdImprovement35434TheFounhImprovement36山東大學(xué)碩士學(xué)位論文點(diǎn)觀察到。加之受無(wú)線傳感網(wǎng)絡(luò)安全通信問(wèn)題的啟發(fā)，人們提出了p路徑頂點(diǎn)覆蓋這一問(wèn)題。此外，無(wú)線傳感網(wǎng)絡(luò)中最優(yōu)鏈路構(gòu)造、各種網(wǎng)絡(luò)環(huán)境中監(jiān)控設(shè)備的安置等問(wèn)題都可以看做是s一路徑頂點(diǎn)覆蓋問(wèn)題在實(shí)際中的應(yīng)用。}路徑頂點(diǎn)
6、覆蓋問(wèn)題是指：蛤定一個(gè)無(wú)向圖和一個(gè)正整數(shù)j，從該圖中找出一個(gè)規(guī)模最小的頂點(diǎn)子集．使得該圖中每條長(zhǎng)度為5-l的路徑至少包含了該頂點(diǎn)子集中的一個(gè)頂點(diǎn)。該問(wèn)題已經(jīng)被證明是NP_完全的。生奎查羔絲±蘭堡絲苧ABSTRACTEachnodeinacomputernetworkpefrormsanumberoftraditionaltasks；generatingmessages，routingandforwardingmessages，consumingmessages，andsoellBut,somenodesinthenetworkafealsodesignatedtop
7、erformadditionaltasks；collectingandanalyzingstatisticsconcerningthemessaget／nl啊cinthenetworkandfilteringtheme女a(chǎn)gntrafficanddiscardinganydetectedattackmessagefromitWerefertothosenodesthatal'edesignatedtoperformtheseadditionaltasksasnetworkobserversIfsnallnodes叢obServernodesinthenetwor
