资源描述：
《on the bottleneck shortest path problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Konrad-Zuse-ZentrumTakustraße7D-14195Berlin-DahlemGermanyfurInformationstechnikBerlin¨VOLKERKAIBELMATTHIASA.F.PEINHARDTOntheBottleneckShortestPathProblemSupportedbytheDFGResearchCenterMATHEONinBerlinZIB-Report06-22(May2006)ONTHEBOTTLENECKSHORTESTPATHPROBLEMVOLKERKAIBELANDMATTH
2、IASA.F.PEINHARDTAbstract.TheBottleneckShortestPathProblemisabasicprobleminnetworkoptimization.Thegoalistodeterminethelimitingcapaci-tyofanypathbetweentwospecifiedverticesofthenetwork.Thisisequivalenttodeterminingtheunsplittablemaximumflowbetweenthetwovertices.Inthisnoteweanalyze
3、thecomplexityoftheproblem,itsrelationtotheShortestPathProblem,andtheimpactoftheunderlyingmachine/computationmodel.1.IntroductionTheBottleneckShortestPathProblem(BSP)isatthecoreofanumberofnetworkoptimizationproblems.Theperformanceofalgorithmsforitissometimescrucialfortherunning
4、timesofalgorithmsforhigherlevelprob-lemsinwhichitoccursasasubproblem.Twoexamplesarethek–splittableflowproblem[4](wheretherunningtimeoftheunderlyingBSPalgorithmappearsasafactorintheworstcaserunningtimeboundofthepresentedalgorithm)andtheMaxFlowProblem[2,Chapter7].Asoutlinedin[2],
5、theasymptoticalworstcasebehaviouroftheEdmonds–KarpalgorithmcannotbeimprovedbyusingaBSPalgorithmforfindingaugmentingpaths,butitmightstillimprovethepracticalperformance.Westartwithaformaldefinitionoftheproblem.LetG=(V,E)beagraph,eitherdirectedorundirected,withintegraledgeweightsce
6、∈Nforalledgese∈E.Thecapacitybpofapathp(viewedasasetofedges)isgivenbybp:=mine∈pce.(Fortheemptypath,wedefineb∅=∞.)Withrespecttosomefixedstartvertexvertexs∈V,thebottleneckbvofavertexv∈Visbv:=maxpbp,whereprangesoverall(directed)pathsstartinginsandendinginv.Anedgethatdeterminesthecap
7、acityofapathorthebottleneckofavertex(i.e.,anedgeforwhichthecorrespondingminimumisattained)iscalledcriticalforthepathorvertex,respectively.TheBottleneckShortestPathProblem(BSP)istodetermine,foragivengraphG=(V,E),edgeweightsce∈N(e∈E),andastartvertexs∈V,thebottleneckbtofsomespeci
8、fiedtargetvertext.Ifwearegiventhebottle-neckbtofsomevertextthe
