资源描述：
《基于原始对偶方法求解网络流量监测集算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、刘湘辉等:基于原始对偶方法求解网络流量监测集算法845ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.17,No.4,April2006,pp.838-844http://www.jos.org.cnDOI:10.1360/jos170838Tel/Fax:+86-10-62562563©2006byJournalofSoftware.Allrightsreserved.基于原始对偶方法求解网络流量监测集算法*SupportedbytheNationalNaturalScience
2、FoundationofChinaunderGrantNo.60373023(国家自然科学基金)Received2004-11-22;Accepted2005-07-11刘湘辉1,2+,殷建平1,卢锡城1,蔡志平1,赵建民31(国防科学技术大学计算机学院,湖南长沙410073)2(国防科学技术大学电子科学与工程学院,湖南长沙410073)3(浙江师范大学计算机学院,浙江金华321004)AlgorithmfortheNetworkFlowMonitoringSetBasedonPrimal-DualMethodLIUXiang-Hui1,2+,YINJian-Ping1
3、,LUXi-Cheng1,CAIZhi-Ping1,ZHAOJian-Min31(SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha410073,China)2(SchoolofElectronicScienceandEngineering,NationalUniversityofDefenseTechnology,Changsha410073,China)3(SchoolofComputerScience,ZhejiangNormalUniversity,Jinhua321004,China)
4、+Correspondingauthor:Phn:+86-731-4573675,Fax:+86-731-4573675,E-mail:LiuXh@tom.comLiuXH,YinJP,LuXC,CaiZP,ZhaoJM.Algorithmforthenetworkflowmonitoringsetbasedonprimal-dualmethod.JournalofSoftware,2006,17(4):838-844.http://www.jos.org.cn/1000-9825/17/838.htmAbstract:Efficientlymonitoringthen
5、etworkflowisimportanttoavarietyofnetworkapplications.Consideringtheequationofflowconservation,theproblemofefficientmonitoringisregardedastheproblemoffindingouttheminimumweakvertexcoversetandtheminimumweakvertexcoversetbasedonflowpartitionforagivengraphG(V,E)whichareallprovedNP-Complete.F
6、irstlytheconstraintsofweakvertexcoversetareanalyzedandtheintegerprogrammingformulationforitisgiven.Nextanapproximationalgorithmfortheminimumweakvertexcoversetproblemisconstructedandtheapproximationratioof2byprimal-dualmethodisanalyzed.Finallytheapproximationalgorithmfortheminimumweakvert
7、excoversetisanalyzedbasedonthemaximalflowpartition.Keywords:weakvertexcover;NP-hard;approximationalgorithm;flowconservation摘要:考虑网络节点的流守恒特性,网络流量的有效监测问题可抽象为求给定图G(V,E)的最小弱顶点覆盖集的问题和基于流划分的最小弱顶点覆盖集的问题,这是NP难的问题.首先分析了弱顶点覆盖集的约束关系,并给出了问题的整数规划形式.然后利用原始对偶方法构造了求解最小弱顶点覆盖集的近似算法,并分析了算法的比
