资源描述：
《approximating layout problems on geometric random graphsnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ApproximatingLayoutProblemsonGeometricRandomGraphs(Extendedabstract)yzyyJosepDazMathewD.PenroseJordiPetitMaraSernaOctober13,1998AbstractWeshowtwosimplealgorithmsthat,withhighprobability,approximatewithinaconstantseverallayoutproblemsforgeometricrandomgraphsdrawnfromtheG(r)npmodelw
2、ithr=clogn=nforanyconstantc6.Thelayoutproblemsthatweconsiderare:Bandwidth,MinimumLinearArrangement,MinimumCut,MinimumSumCut,VertexSeparationandBisection.ThisresearchwaspartiallysupportedbyESPRITLTRProjectno.20244
3、ALCOM-IT,CICYTProjectTIC97-1475-CE,andCIRITproject1997SGR-00366.yDepart
4、amentdeLlenguatgesiSistemesInformatics.UniversitatPolitecnicadeCatalunya.CampusNordC6.c/JordiGirona1-3.08034Barcelona(Spain).fdiaz,jpetit,mjsernag@lsi.upc.eszDepartmentofMathematicalSciences,UniversityofDurham,SouthRoad,DurhamDH13LE,England.Mathew.Penrose@durham.ac.uk1IntroductionSev
5、eralwell-knownoptimizationproblemsongraphscanbeformulatedasLayoutProblems.Theirgoalisto ndalayout(linearordering)ofthenodesofaninputgraphsuchthatacertainfunctionisminimized.Layoutproblemsareanimportantclassofproblemswithmanydi erentapplicationsinComputerScience,Biology,Archaeology,Line
6、arAlgebra,etc(confertoReferencesformotivation,inparticular[8]).FindinganoptimallayoutisNP-hardingeneral,andthereforeitisnaturaltodevelopandanalyzeecientheuristicsthatgivegoodapproximationsinpractice.Astandardwayofevaluatingtheeciency(fromapracticalpointofview)ofanheuristicalgorithmis
7、toevaluateitsperformanceonrandominstances.Twoclassesofrandominstanceshavebeenwidelyusedintheliteraturetoenablecomparisonsofalgorithmsforlayoutandpartitioningproblems:randomgraphsandgeometricrandomgraphs.WedenotetheformerclassbyG,wherenrepresentsthenumberofnodesandpistheprobabilityn;pof
8、theexistenceofeachpossibleedge.WedenotetheclassofgeometricrandomgraphsasG(r),wherenisthenumberofverticesandriscalledtheradius.Theverticesofageometricnrandomgraphcorrespondtonpointsrandomlydistributedontheunitsquare.Eachofitspossibleedgesappearsifandonlyifthe(Euclidean)distancebetween
