copyright c00185

《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