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