s--路径顶点覆盖问题的算法研究

《s--路径顶点覆盖问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、14文章组织结构6第二章争路径顶点覆盖问题的研宄72l}路径顶点覆盖问题721ls．路径顶点覆盖问题的复杂性72,2树上的争路径顶点覆盖问题的擐优算法82,3本章小结9第三章3．路径顶点覆盖问题的算法研究103I3-路径顶点覆盖10323．路径顶点覆盖问题的一个最优算法lo3．33-路径顶点覆盖问题算法的改进13331算法的第一次改进13332算法的第二次改进153．33算法的第三次改进⋯⋯15334算法的第四次改进173．35算法的第五次政进⋯1934本章小结⋯24第四章4．路径顶点覆盖问题的算法研究264I4-路径顶点覆盖26424-路径顶点覆盖问题的一个最优算

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山东大学硕士学位论文点观察到。加之受无线传感网络安全通信问题的启发，人们提出了p路径顶点覆盖这一问题。此外，无线传感网络中最优链路构造、各种网络环境中监控设备的安置等问题都可以看做是s一路径顶点覆盖问题在实际中的应用。}路径顶点

6、覆盖问题是指：蛤定一个无向图和一个正整数j，从该图中找出一个规模最小的顶点子集．使得该图中每条长度为5-l的路径至少包含了该顶点子集中的一个顶点。该问题已经被证明是NP_完全的。生奎查羔丝±兰堡丝苎ABSTRACTEachnodeinacomputernetworkpefrormsanumberoftraditionaltasks；generatingmessages，routingandforwardingmessages，consumingmessages，andsoellBut,somenodesinthenetworkafealsodesignatedtop

7、erformadditionaltasks；collectingandanalyzingstatisticsconcerningthemessaget／nl啊cinthenetworkandfilteringtheme女agntrafficanddiscardinganydetectedattackmessagefromitWerefertothosenodesthatal'edesignatedtoperformtheseadditionaltasksasnetworkobserversIfsnallnodes丛obServernodesinthenetwor