A Simple 3-Edge-Connected Component Algorithm

《A Simple 3-Edge-Connected Component Algorithm 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、TheoryComput.Systems40,125–142(2007)TheoryofDOI:10.1007/s00224-005-1269-4ComputingSystems©2005SpringerScience+BusinessMedia,Inc.ASimple3-Edge-ConnectedComponentAlgorithm∗YungH.TsinSchoolofComputerScience,UniversityofWindsor,Windsor,Ontario,CanadaN9B3P4pete

2、r@cs.uwindsor.caAbstract.Asimplelinear-timealgorithmforfindingallthe3-edge-connectedcomponentsofanundirectedgraphispresented.Thealgorithmperformsonlyonedepth-firstsearchoverthegivengraph.Previouslybestknownalgorithmsperformmultipledepth-firstsearchesinmultipl

3、ephases.1.IntroductionThenotionofk-vertex-connectivityandk-edge-connectivityareintroducedtomea-suretheextenttowhichagraphisconnected.Forundirectedgraphs,linear-timeal-gorithmsareknownonlyfork=2or3forbothvertex-andedge-connectivity.Tar-janpresentedasimplean

4、delegantlinear-timealgorithmfor2-vertex-connectivity[8].Hisalgorithmisbasedonthepowerfulgraphtraversaltechnique,depth-firstsearch,whichwasdiscoveredbyHopcroftandhimself.Thealgorithmalsosolvesthe2-edge-connectivityprobleminlineartime.Gabowrevisiteddepth-first

5、searchfromadifferentperspective[2]—thepath-basedview—andpresentednewelegantlinear-timealgorithmsfor2-edge-connectivityand2-vertex-connectivity.For3-vertex-connectivity,HopcroftandTarjanpresentedalinear-timealgorithm[5].Theiralgorithmisalsobasedondepth-first

6、search.For3-edge-connectivity,thefirstlinear-timealgorithmwaspresentedbyGalilandItaliano[3].Theirmethodistoreduce3-edge-connectivityto3-vertex-connectivityinlineartimeandthenuseHopcroftandTarjan’slinear-timealgorithmfor3-vertex-connectivitytosolvetheproblem

7、.Therefore,theiralgorithmisbasedonreductionanddepth-firstsearch.Twosimplerlinear-timealgorithmswerethenreportedbyTaokaetal.[7]andNagamochiandIbaraki[6].Bothalgorithmsalsousedepth-firstsearch.∗ThisresearchwaspartiallysupportedbyNSERCunderGrantNSERC-781198.126

8、Y.H.TsinTaokaetal.[7]computethe3-edge-connectedcomponentsinthreephasesandperformsfourdepth-firstsearchesonthegivengraph.Theydividecut-pairs(apairofedgeswhoseremovaldisconnectsthegivengraph)intotwotypes:type-1a