欢迎来到天天文库
浏览记录
ID:34577584
大小:327.12 KB
页数:33页
时间:2019-03-08
《copyright c00185》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、BRICSBasicResearchinComputerScienceBRICSRS-00-21Moller&Alur:HeuristicsforHierarchicalPartitioning¨HeuristicsforHierarchicalPartitioningwithApplicationtoModelCheckingM.OliverMoller¨RajeevAlurBRICSReportSeriesRS-00-21ISSN0909-0878August2000Copyrightc2000,M.OliverMolle
2、r&RajeevAlur.¨BRICS,DepartmentofComputerScienceUniversityofAarhus.Allrightsreserved.Reproductionofallorpartofthisworkispermittedforeducationalorresearchuseonconditionthatthiscopyrightnoticeisincludedinanycopy.SeebackinnerpageforalistofrecentBRICSReportSeriespublicat
3、ions.Copiesmaybeobtainedbycontacting:BRICSDepartmentofComputerScienceUniversityofAarhusNyMunkegade,building540DK–8000AarhusCDenmarkTelephone:+4589423360Telefax:+4589423255Internet:BRICS@brics.dkBRICSpublicationsareingeneralaccessiblethroughtheWorldWideWebandanonymou
4、sFTPthroughtheseURLs:http://www.brics.dkftp://ftp.brics.dkThisdocumentinsubdirectoryRS/00/21/HeuristicsforHierarchicalPartitioningwithApplicationtoModelCheckingM.OliverM¨oller†andRajeevAlur‡†BRICS‡UniversityofPennsylvaniaDepartmentofComputerScienceComputer&Informati
5、onScienceUniversityofAarhusMoorebuildingNyMunkegade,building540200South33rdStreetDK-8000˚ArhusC,DenmarkPhiladelphia,PA19104,USAomoeller@brics.dkalur@cis.upenn.edu30August2000AbstractGivenacollectionofconnectedcomponents,itisoftendesiredtoclustertogetherpartsofstrong
6、correspondence,yieldingahierarchicalstructure.Weaddresstheau-tomationofthisprocessandapplyheuristicstobattlethecombinatorialandcompu-tationalcomplexity.Wedefineacostfunctionthatcapturesthequalityofastructurerelativetotheconnectionsandfavorsshallowstructureswithalowde
7、greeofbranching.FindingastructurewithminimalcostisshowntobeNP-complete.Wepresentagreedypolynomial-timealgorithmthatcreatesanapproximativegoodsolutionincrementallybylocalevaluationofaheuristicfunction.Wecomparesomesimpleheuristicfunc-tionsandargueforonebasedonfourcri
8、teria:Thenumberofenclosedconnections,thenumberofcomponents,thenumberoftouchedconnectionsandthedepthofthestructure.Wereportonanapplicationi
此文档下载收益归作者所有