欢迎来到天天文库
浏览记录
ID:36633198
大小:1.09 MB
页数:56页
时间:2019-05-13
《树的核与中心的并行算法研究》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、分类号UDCY855800密级单位代码树的核与中心的并行算法研究王燕1015l指导教师王德强职称教授学位授予单位大连海事大学申请学位级别硕士学科与专业应用数学论文完成日期2006年2月论文答辩日期;!!!生!旦!!答辩委员会主席EfficientParallelAlgorithmsforCoreandCenterofaTreeNetworkAbstractLocationtheoryisconcernedwithoptimallocationotfacilitiesonagivennetwork,whichcanbcseenassinglepoints.However,inmanyr
2、ealapplications,thefacilitytobelocatedistoolargetobcmodeledasapoint.Thatwillcallthesekindsoffacilitiesextensivefacilitieswhichhavetheformofapathorofatree.Optimallylocatingafacilityinanetworkisanimportantprobleminthefieldsoftransportationandcommunication.So,manyresearchershavepaidtheirattentiont
3、othesefields.Thecriteriaforoptimalityextensivelystudiedintheliteraturearetheminimumeccentricityandtheminimumdistancesumcriterion.Thecriteriaforoptimalityextensivelystudiedintheliteraturearetheminimumeccentricitycriterioninwhichthedistancetothefarthestvertexfromthefacilityisminimizedandtheminimu
4、mdistancesumcriterioninwhichthetotaldistancefromthefacilitytotheverticesisminimized.Inthispaper,webaseontheminimumeccentricityandtheminimumdistancesumcriterionofoptimalitycriterions.Westudythesealgorithmswhichpiek-treecenter,k-treecore@,f)一coreand俅,f)Icenterofatreenetwork.GivenatreeLAk-treecent
5、erofTisaminimumeccentricitysubtreeofLwhichcontainsexactlykleaves.Ak-treecoreofTisaminimumdistancesumsubtreeofLwhichcontainsexactlykleaves.Weconsidertheproblemofselectingasubtreewithexactlykleavesandwithadiameterofatmostf,whichminimizesthedistancefromthefarthestvertextothesubtree.Wecallsuchasubt
6、reethe@f)一ceDterofT.AsubtreeofTwithatmostkleavesandwithadiameterofatmostfwhichminimizesthesumofthedistanceoftheverticesfromtheselectedsubtree,thissubtreecalla@,,)一coreof—Inthispaper,weapplytheEuler-tourtechnique,treecontractionandupwardtreeaccumulation.Weproposefourefficientparallelalgorithmsto
7、solvek-treecenter,k-treecore,@,,)_coreand@妒centerofLrespectively.ThealgorithmsweproposedtakeO(109n)timeusingO(n)workontheEREWPRAM.Furthermore,westudythepropertiesofthesequestions.ThealgorithmsofthispaperVimprovethealgorithmsofWang
此文档下载收益归作者所有