computationgraph

HALId:tel-01273352https://hal.
inria.
fr/tel-01273352Submittedon12Feb2016HALisamulti-disciplinaryopenaccessarchiveforthedepositanddisseminationofsci-entificresearchdocuments,whethertheyarepub-lishedornot.
ThedocumentsmaycomefromteachingandresearchinstitutionsinFranceorabroad,orfrompublicorprivateresearchcenters.
L'archiveouvertepluridisciplinaireHAL,estdestinéeaudéptetàladiffusiondedocumentsscientifiquesdeniveaurecherche,publiésounon,émanantdesétablissementsd'enseignementetderecherchefranaisouétrangers,deslaboratoirespublicsouprivés.
GraphSearcheswithApplicationstoCocomparabilityGraphsJérémieDusartTocitethisversion:JérémieDusart.
GraphSearcheswithApplicationstoCocomparabilityGraphs.
ComputerScience[cs].
UniversitéDenisDiderotParis7,2014.
English.
tel-01273352UNIVERSITEPARIS.
DIDEROT(Paris7)SORBONNEPARISCITEECOLEDOCTORALE:386–SciencesMathematiquesdeParisCentreLaboratoired'InformatiqueAlgorithmique:FondementsetApplications(LIAFA)DOCTORATINFORMATIQUEDUSARTJeremieGraphSearcheswithApplicationstoCocomparabilityGraphsParcoursdegraphes,applicationssurlesgraphesdecocomparabiliteTh`eseco-dirigeeparMichelHabib,Professeur(UniversiteParisDiderot)etDerekCorneil,Professeur(UniversityofToronto)Soutenuele24juin2014JURYDirecteursdeth`ese:MichelHabibDerekCorneilRapporteurs:LhouariNourineChristophePaulExaminateurs:EkkehardK¨ohlerMauricePouzetLaurentViennotiiAcknowledgementsIwouldliketothankmysupervisorsMichelandDerek.
Iamgratefulfortheirsupports,advices,discussions,helpwiththeEnglish(es-peciallyDerekonthispoint)andlettingmepursueresearchinanindependentway.
IalsowouldliketothankDerekforitsinvitationstoToronto,acitywhereImetmanypeoplewhohadorgoingtohaveabiginuenceonme.
IwishtothankChristophePaulandLhouariNourineforreadingmythesisandwritingareport.
Idon'tforgetalsoMauricePouzet,LaurentViennotandEkkehardK¨ohlerforacceptingtobepartofthejury.
IamalsohappytothankalltheotherpeopleImetduringmymasterinternshipandmyphdintheLIAFA:theresearchers,teachers,staandofcoursetheotherphdstudents.
Ihadalotoffunmomentsthere.
Finally,IwillalsothankmyfamilyandfriendsoutsidetheLI-AFA.
iiContentsIntroduction10.
1Contentofthethesis20.
2Contributions31GraphSearchincocomparabilitygraphs51.
1Introduction51.
2GraphSearchParadigm51.
3Classicalgraphsearches71.
3.
1GenericSearch(GENS)71.
3.
2Breadth-FirstSearch(BFS)81.
3.
3Depth-FirstSearch(DFS)91.
3.
4LexicographicBreadth-FirstSearch(LBFS)91.
3.
5LexicographicDepth-FirstSearch(LDFS)111.
3.
6MaximalNeighborhoodSearch(MNS)121.
3.
7MaximalCardinalitySearch(MCS)131.
3.
8Hierarchyofgraphsearches131.
4Comparability,cocomparabilityandintervalgraphs141.
4.
1Cocomparabilityandcomparability141.
4.
2Intervalgraphs161.
5Graphsearchincocomparabilitygraphs171.
5.
1Controllingtie-breakingvia"+"sweeps17iii1.
5.
2Graphsearchesthatmaintainacocomporderingwhenusedasa"+"sweep181.
6Consequences212AnewcharacterizationtheoremforCocomparabilityGraphs232.
1Introduction232.
2Themaximalantichainlatticeofapartialorder(MA(P)232.
3ExtrapropertiesofMA(P)262.
4Cliquesstructureofcocomparabilitygraphs282.
5Conclusionandperspectivesforfurtherwork333Intervalsubgraphsofcocomparabilitygraphs353.
1Introduction353.
2Spanningintervalgraphs363.
3ComputingamaximalchainofMA(P)403.
4Maximalchordalandintervalsubgraphs473.
5Maximumintervalsubgraph523.
6Conclusionsandperspectivesforfurtherwork534Simplicialverticesandcliqueseparatorsincocomparabilitygraphs554.
1Introduction554.
2FullycomparablecliqueandMNSordering564.
3Simplicialverticesincocomparabilitygraphs584.
4Minimalcliqueseparatorsincocomparabilitygraphs604.
4.
1Theproblemofminimalcliqueseparators604.
4.
2Cliqueseparatorsandcomponentsincocomparabilitygraphs624.
4.
3Structureoftheatomsofacocomparabilitygraph674.
4.
4CorrectnessoftheAlgorithm704.
5Conclusionsandperspectivesforfurtherwork735TransitiveOrientation:MultisweepLBFS755.
1Introduction755.
2SeriesofLBFS765.
3ProofofRepeatedLBFS+Algorithm77iv5.
3.
1Sketchoftheproofofourmainresult775.
3.
2Denitionsandnotations785.
3.
3Theproof785.
4Conclusionsandperspectivesforfurtherwork906TBLS:anewmodelforgraphsearch936.
1Introduction936.
2TBLS,aTie-BreakingLabelSearch946.
3CharacterizingclassicalsearchesusingTBLS966.
3.
1GenericSearch976.
3.
2BFS(Breadth-FirstSearch)986.
3.
3DFS(DepthFirstSearch)996.
3.
4LBFS(LexicographicBreadthFirstSearch)996.
3.
5LDFS(LexicographicDepthFirstSearch)1006.
3.
6LimitationsoftheTBLSmodel1016.
4Twonewlexicographicsearches1026.
4.
1LexUP1026.
4.
2LexDOWN1046.
5TBLShierarchyofsearches1066.
6TherelationshipbetweenGLSandTBLS1086.
7Test,certicationandimplementation1116.
7.
1TestingaTBLS1116.
7.
2Certifyingthatanorderingisproducedbyagivensearch.
1126.
7.
3Implementation1136.
8Application:theTBLSdimension,anewgraphparameter.
.
.
.
1156.
9Concludingremarks116ANotation119A.
1Setsandbinaryrelations119A.
2Graphs119A.
3Orders121References125vListofAlgorithms131viIntroductionAgraphsearchisamechanismforsystematicallyvisitingtheverticesofagraph.
Ithasbeenafundamentaltechniqueinthedesignofgraphalgorithmssincetheearlydaysofcomputerscience.
ManyoftheearlysearchmethodswerebasedonBreadthFirstSearch(BFS)orDepthFirstSearch(DFS)andresultedine-cientalgorithmsforpracticalproblemssuchasthedistancebetweentwovertices,diameter,connectivity,networkowsandtherecognitionofplanargraphssee[CLRS01].
Manyvariantsofthesesearcheshavebeenintroducedsince,providingelegantandsimplesolutionstomanyproblems.
Forexample,LexicographicBreadthFirstSearch(LBFS)[RTL76],anditsgeneralizationMaximalNeighborhoodSearch(MNS)[Shi84]wereshowntoyieldsimplelineartimealgorithmsforchordalgraphrecognition.
SincethenmanynewapplicationsofLBFShavebeenpresentedrangingfromrecognizingvariousrestrictedfamiliesofgraphstondingverticeswithhigheccentricityortondingthemodulardecompositionofagivengraph,see[Cor04a,COS09].
Eveniftheywereknownforquitesometime,itisonlyrecentlythattheyhavebeenconsideredasubjectofitsown.
Therstpapertodoitmustbe[CK08].
Init,theauthorsstudiedthegraphsearchandcharacterizetheorderingtheyproduce.
Doingso,theyintroducedLexicographicDepthFirstSearch(LDFS)basedonitssymmetrywithLBFS.
AfewyearsafteritsdiscoveryitwasshownthatLDFSwhenappliedtococomparabilitygraphsyieldssimpleandecient1CONTENTSalgorithmsforsolvingvariousHamiltonianPathrelatedproblems[CDH13,MC12,CDHK].
Forageneralstudyofgraphsearch,itmustalsobecited[KSB11,Kru05]wheretheauthorsintroducedframeworkstocapturetheclassicalgraphsearches.
Thepurposedofthisthesisistoaugmenttheseresults.
Thebasicdenitionsandnotationsusedinthisthesisarequitestandard.
Forthereaderunfamiliarwithgraphorordertheories,theycanbefoundinAppendixA.
Inthisthesis,unlessotherwisestated,theobjects(graph,partialorder.
.
.
)arenite.
0.
1ContentofthethesisInchapter1,wepresentaformaldenitionofgraphsearch,reviewtheprincipalgraphsearchesandshowhowtheytintheformalism,makeabriefsurveyofcocomparabilitygraphsandintervalgraphs,andpresentsomeresultsongraphsearchesandcocomparabilitygraph.
Theseresultswerethemainmotivationofthestudyofcocomparabilitygraphsfromagraphsearchpointofview.
Chapter2isdedicatedtoanewcharacterizationtheoremforcocomparabilitygraphs.
Thistheoremstatesthatthesetofmaximalcliquesofacocomparabilitygraphcanbeequippedwithalatticestructurerespectingsomeproperties.
Thistheoremcanbeseenasanextensionofthetheoremthatstatesthatagraphisanintervalgraphifandonlyifthereexistsalinearorderingonitsmaximalcliques.
Inchapter3wedevelopanalgorithmtocomputeamaximalchainofthelatticestructureofacocomparabilitygraph.
ThisalgorithmgivesusawaytondaminimalintervalextensionofapartialorderbutalsoamaximalintervalandmaximalchordalsubgraphinO(n2)inaverysimplefashion.
Withthisalgorithmwecanseethatgraphsearchcanbeofgreathelptodesignsimplealgorithms.
Attheendofthechapter,wedealwiththeproblemofcomputingamaximumintervalsubgraph.
Chapter4isdedicatedtosolvingtheproblemofndingthesimplicialverticesofacocomparabilitygraphandtheproblemofndingadecompositionofacocomparabilitygraphusingthecliqueseparators.
Inbothcases,wepresentalineartimealgorithmtosolvetheproblem.
Sofarthesecasearetheonlyalgorithmsknownfortheseproblemsthatruninlineartimeforagraphclass20.
2Contributionsdierentfromthechordalgraphclass.
Acliqueseparatorbaseddecompositionallowsustouseadivideandconquerapproachforproblemslikemaximumcliqueoroptimalcoloring.
Thisresultimpliesanewwaytodecomposeapartialorderwithgoodalgorithmicperspectives.
Inchapter5,wepresentanalgorithmtondacocomporderingorequivalentlyatransitiveorientation.
Thisalgorithmanswerspositivelyaquestionaskedin[COS09],namelywhetherthereexistsamultisweepalgorithmbasedonLBFStondacocomporderingofacocomparabilitygraph.
Chapter6isdedicatedtothepresentationofaframeworkpowerfulenoughtocapturemanygraphsearcheseitherusedindividuallyorinamulti-sweepfashionandsimpleenoughtoallowgeneraltheoremsongraphsearches.
BuildingontheGeneralLabelSearch(GLS)frameworkfrom[KSB11]wenotonlysimplifytheirmodelbutalsounifytheirmodelwiththe"pattern-conditions"formalismof[CK08].
0.
2ContributionsChapter1containsthepresentationofavariationofanoriginalworkdonebyDerekCorneil,MichelHabibandEkkehardKohler.
Chapters2,3,4containworkdoneincollaborationwithMichelHabib.
Thecontentsofthosechaptersformsthesubjectofanarticleinpreparation[CDHK].
Chapter5containsworkdonewithMichelHabibandsubmitted[DH].
Chapter6containsworkdoneincollaborationwithDerekCorneil,MichelHabib,AntoineMamcarz,FabiendeMontgolerandsubmitted[CDH+].
3CONTENTS41GraphSearchincocomparabilitygraphs1.
1IntroductionSinceourworkdealswithgraphsearch,westartbyformalizingwhatwemeanbyagraphsearch.
ItwillbedonethroughtheintroductionoftheGraphSearchParadigminsection1.
2.
Insection1.
3,wereviewsomeclassicalgraphsearchesandshowhowtheytintheGraphSearchParadigm.
Weusetheopportunitytorecallsomeoftheimportantresultsaboutthegraphsearchesthatinterestus.
Insection1.
4,weintroducethecomparability,cocomparabilityandintervalgraphs.
Insection1.
5,wepresentresultsaboutgraphsearchesincocomparabilitygraphs.
Theseresultsconstituteanimportantbasisfortheapplicationsincocomparabil-itygraphsandwerethemainmotivationofthestudyofcocomparabilitygraphsfromagraphsearchpointofview.
ThischapterisdedicatedtothepresentationofavariationofaworkdonebyDerekCorneil,MichelHabibandEkkehardKohler.
1.
2GraphSearchParadigmAgraphsearch"visits"theverticesofthegivengraphinavertex-by-vertexfashionandthechoiceofthenextvertextovisitisdeterminedbypropertiesoftheverticesalreadyvisited.
Toformalizesuchanalgorithm(presentedbelowastheGraphSearchParadigm)weimposethefollowingconditions:ConditionsfortheGraphSearchParadigm(GSP):51.
GRAPHSEARCHINCOCOMPARABILITYGRAPHS1.
AtanytimeduringthesearchweletXdenotethesetofcurrentlyvisitedvertices;initiallyXisthenullset.
Fornotationalconvenience,Vunvisited=V(G)Xdenotesthecurrentlyunvisitedvertices.
2.
Duringtheexecutionofthealgorithm,wedenotethesetofverticeseligibletobevisitednextasEligible;initiallyEligibleisV(G).
Weputthecondi-tionthatforallu,v∈Vunvisited,ifN(u)∩X=N(v)∩XtheneitheruandvarebothinEligibleortheyarebothnotinEligible(i.
e.
,theyarebothinVunvisitedEligible).
WecalledthisconditionLeftTwinCompatible(LTC).
3.
Forallstepsofthealgorithm,werequireEligible=.
ItshouldbenotedthatwedonotputanyconditiononhowthesetEligibleiscomputedandwhataretheinformations,dataused.
ItisnotnecessarilyafunctionofX.
WeonlywanttheLTCconditiontoberespected.
TheLTCconditioncanbeseenasafairnesscondition,i.
e.
twoverticessimilarfromthepointofviewofthevisitedverticescannotbedistinguished.
Itshouldbenotedthatwedonotputanyconditionontheconnectivityofthegraph.
Thegraphcanbedisconnected.
Condition3impliesthatthesearchknowswhattodointhecaseofadisconnectedgraph.
Thethirdconditionimmediatelyyieldsthefollowingproperty:Proposition1.
2.
1.
EverygraphsearchSsatisfyingtheGraphSearchParadigmwhenappliedtoagraphoutputsanorderingS(σ)ofthevertices.
AlthoughthedescriptionofhowEligibleiscomputedisenoughtospecifytheparticularsearch,manygraphsearchesarecloselyidentiedwiththedatastructuresthatareusedintheirimplementations.
Toacknowledgethisrelation-ship,inourGraphSearchParadigmweintroduceadata-structureDusedbythealgorithmasDandletD(X)representthestatusofDatthestagewhenXisthesetofvisitedvertices.
WerequirethatD(X)storesasubsetofVunvisitedandthatallverticesinEligiblemustbepresentinD(X).
FurthermorenotethattheGraphSearchParadigmissilentonhowtherstlineoftheloop"chooses"vfromEligiblewhen|Eligible|>1.
Insuchacase"tie-breaking"issettohave61.
3Classicalgraphsearchesoccurred.
Atthispoint,weassumethateveryvertexinEligibleiseligibletobechosen.
Insubsection1.
5.
1wewilldescribeamoresophisticated"tie-breaking"mechanism.
Algorithm1:GraphSearchParadigm(GSP).
Input:AgraphG=(V(G),E(G))Output:anorderingσofV(G)whereσ(i)isthei'thvertexvisitedX←%{Xisthesetofvisitedvertices}%;Vunvisited←V(G)%{Vunvisitedisthesetofunvisitedvertices}%;Eligible←V(G)%{allverticesareeligibletobevisitedrst}%;InitializedatastructureD();fori=1tondoComputeEligiblefromD(X)andchoosevfromEligibletobethenextvisitedvertex;σ(i)←v;Vunvisited←Vunvisited{v};X←X∪{v};UpdateD(X);end1.
3ClassicalgraphsearchesToillustratetheGraphSearchParadigm(GSP),wereviewtheclassicalsearchesGenericSearch(GENS),Breadth-FirstSearch(BFS)andDepth-FirstSearch(DFS),their"lexicographic"variantsLBFSandLDFS,MaximalNeighborhoodSearch(MNS)andMaximalCardinalitySearch(MCS).
1.
3.
1GenericSearch(GENS)AGenericSearchasdescribedbyTarjan[Tar72]isanysearchthatwhereverpossiblevisitsaneighborofanalreadyvisitedvertex.
Therefore,atanystepEligible={x∈Vunvisited|v∈Xandx∈N(v)}.
Thisdescribesthegeneric71.
GRAPHSEARCHINCOCOMPARABILITYGRAPHSsearchinthecaseofaconnectedgraph.
Todealwithdisconnectedgraphs,wehavetoputtheextraconditionthatifEligible=thenEligible=Vunvisited.
Thereexistsacharacterizationofagenericsearchordering:Theorem1.
3.
1.
[CK08]LetG=(V(G),E(G))beagraphandσanorderingofV(G).
Thefollowingconditionsareequivalent:1.
σisagenericsearchorderingofV(G).
2.
Foreverytripleofverticesa,b,csuchthataSearch(BFS)Wenowfocusonthewell-knownBreadth-FirstSearch(BFS).
BFSisarestrictionofGenericSearchinthesensethatBFSwillalwayschooseavertexwithavisitedneighborwhereverispossible.
ThereforeeveryBFSorderingisagenericsearchordering.
Buttheconverseisnottrue.
BFSismorepickyonthesetEligible.
EligibleistheneighborhoodinVunvisitedoftheearliestvisitedvertexinXhavinganeighborinVunvisited.
Tohandlethecaseofdisconnectedgraphs,againwesettheconditionthatinthecasewhereeveryvertexofXdoesnothaveaneighborinVunvisited,thenEligible=Vunvisited.
AcharacterizationofaBFSorderingexists:Theorem1.
3.
2.
[CK08]LetG=(V(G),E(G))beagraphandσanorderingofV(G).
Thefollowingconditionsareequivalent:1.
σisaBFSordering.
2.
foreverytriplea,b,c∈Vsuchthatagraphsearches1.
3.
3Depth-FirstSearch(DFS)WenowturnourattentiontoDepth-FirstSearch(DFS).
DFS,asBFS,isalsoarestrictionofGenericSearch.
ThedierencebetweenDFSandGenericSearchliesagaininthecomputationofEligible.
EligibleistheneighborhoodinVunvisitedofthelatestvisitedvertexofXhavinganeighborinVunvisited.
Tohandlethecaseofdisconnectedgraphs,againwesettheconditionthatinthecaseofeveryvertexofXnothavinganeighborinVunvisited,thenEligible=Vunvisited.
ADFSorderingcanbecharacterized:Theorem1.
3.
3.
[CK08]LetG=(V(G),E(G))beagraphandσanorderingofV(G).
Thefollowingconditionsareequivalent:1.
σisaDFSordering.
2.
foreverytripleofverticesa,b,csuchthatagraphicBreadth-FirstSearch(LBFS)TheLexicographicBreadth-FirstSearch(LBFSorLexBFS)wasrstintroducedin[RTL76]torecognizechordalgraphs.
Sincethen,manynewapplicationsofLBFShavebeenpresentedrangingfromrecognizingvariousrestrictedfamiliesofgraphstondingverticeswithhigheccentricityortondingamodulardecompo-sitionofagivengraph,see[Cor04a,COS09,Cor04b,BCHP08,TCHP08,LW13,DH].
TheLBFSalgorithmassignslabeltoeachvertexthatarewordsoverthealphabet{0,.
.
.
,n1,n}andtheemptywordisrepresentedby.
Ateachstep,avertexwithlexicographiclargestlabelischosenandthelabelofitsneighborsisupdated.
Therefore,EligibleisthesubsetofVunvisitedhavingthelexicographiclargestlabel.
LetusnowdescribeLBFSbyanalgorithmandthengiveanexample.
Itmustbenotedthatwenumbertheverticesfrom1tonwhereaswhenitwasrstdescribedin[RTL76],theverticeswherenumberedfromnto1.
91.
GRAPHSEARCHINCOCOMPARABILITYGRAPHSAlgorithm2:LBFSData:G=(V(G),E(G))anundirectedgraphResult:anorderingσoftheverticesofG1assignlabeltoallvertices;2for(i=1to|V(G)|)do3pickanyunvisitedvertexuwithlexicographicallylargestlabel;4σ(i)←u%{givetouthenumberi}%;5foreach(unvisitedvertexv∈N(u))do6append|V(G)|itolabel(v);7end8end9Outputσ;ToillustrateLBFS,considerthegraphinFigure1.
1.
ThevalueofthelabelsatthebeginningofeachstepisinthetableofFigure1.
2.
Thestartvertexisdandtheorderingproducedisσ=.
Figure1.
1:AgraphG=(V(G),E(G)).
AcharacterizationofaLBFSorderingexists:Theorem1.
3.
4.
[RTL76,Gol04,BDN97]LetG=(V(G),E(G))beagraphandσanorderingofV(G).
Thefollowingconditionsareequivalent:1.
σisaLBFSordering2.
foreverytriplea,b,c∈V(G)suchthatagraphsearchesvertexi=1i=2i=3i=4i=5i=6dc5b554f555a44343e33232Figure1.
2:Thevalueofthelabelsatthebeginningofeachsteponexample1.
1.
TheeasiestimplementationusespartitionrenementforthemanagementofD(X)(see[HMPV00])andhascomplexityO(n+m).
1.
3.
5LexicographicDepth-FirstSearch(LDFS)TheLexicographicDepth-FirstSearch(LDFSorLexDFS)wasintroducedin[CK08].
Duringquitesometime,LDFShasbeenintroducedbutnoapplicationofitwasknown.
Sincethensomeapplicationshavebeenfound.
Themostnotableonesaretondamaximumpathcoverofacocomparabilitygraph[CDH13]andtondalongestpathincocomparabilitygraphs[MC12].
AsLBFS,LDFSuseslabelsthatarewordsoverthealphabet{0,.
.
.
,n1,n}andtheemptywordisrepresentedby.
Ateachstep,EligibleisthesubsetofVunvisitedhavingthelexicographiclargestlabel.
Thedierencebetweenthetwolieswithinthewayofupdatingthelabelofanunvisitedneighborofthechosenvertex.
InLBFS,weappendniwhereasinLDFSweprependi.
LetusnowdescribeLDFSbyanalgorithmandthengiveanexample.
ToillustrateLDFS,considerthegraphinFigure1.
1.
ThevalueofthelabelsatthebeginningofeachstepisinthetableofFigure1.
3.
Thestartvertexisaandtheorderingproducedisσ=.
ALDFSorderingcanbecharacterized:Theorem1.
3.
5.
[CK08]LetG=(V(G),E(G))beagraphandσanorderingofV(G).
Thefollowingconditionsareequivalent:111.
GRAPHSEARCHINCOCOMPARABILITYGRAPHSAlgorithm3:LDFSData:G=(V(G),E(G))anundirectedgraphResult:anorderingσoftheverticesofG1assignlabeltoallvertices;2for(i=1to|V(G)|)do3pickanyunnumberedvertexuwithlexicographicallyhighestlabel;4σ(i)←u%{givetouthenumberi}%;5foreach(unnumberedvertexv∈N(u))do6prependitolabel(v);7end8end9Outputσ;vertexi=1i=2i=3i=4i=5i=6ab1c121d232f4e22225Figure1.
3:Thevalueofthelabelsatthebeginningofeachsteponexample1.
1.
1.
σisaLDFSordering2.
foreverytriplea,b,c∈VsuchthataSearch(MNS)WenowturnourattentiononMaximalNeighborhoodSearch(MNS).
Ithasbeenintroducedin[Shi84]forchordalgraphsrecognition.
Eligibleisthesubset121.
3ClassicalgraphsearchesofverticesinVunvisitedwhoseneighborhoodinXismaximalwithrespecttoinclusion.
WenowrecallthecharacterizationofaMNSordering.
Theorem1.
3.
6.
[CK08]Thefollowingconditionsareequivalent:1.
σisaMNSordering2.
foreverytriplea,b,c∈VsuchthataSearch(MCS)Tonishwithclassicalsearches,weturnourattentiononMaximalCardinalitySearch(MCS).
Ithasbeenintroducedin[TY84].
EligibleisthesubsetofverticesinVunvisitedthathavethemaximumnumberofneighborsinX.
MCScanbeimplementedwithcomplexityO(n+m)(see[TY84]).
1.
3.
8HierarchyofgraphsearchesAhierarchyexistsamongthegraphsearchescitedinthissection.
Thishierarchyhasrstappearsin[Shi84]andwesummarizeitinFigure1.
4.
Wewillcomebacktothishierarchyinchapter6.
LBFSLDFSMCSMNSBFSDFSGenericSearchFigure1.
4:Summaryoftheheredityrelationshipsprovedintheorem6.
5.
5.
AnarcfromSearchStosearchSmeansthatSextendsS.
131.
GRAPHSEARCHINCOCOMPARABILITYGRAPHS1.
4Comparability,cocomparabilityandinter-valgraphsInthissectionwemakeashortreviewofcomparability,cocomparabilityandintervalgraphs.
Aswewillshowinsection1.
5andlaterinthisthesis,graphsearchesplayanimportantroleinthesegraphclasses.
Foramoredetailedreviewongraphclasses,wereferthereaderto[Gol04].
1.
4.
1CocomparabilityandcomparabilityComparabilityandcocomparabilitygraphsareimportantbothingraphandordertheories.
Tobeabletodenethesefamiliesweneedrsttodenetheconceptoftransitiveorientation.
Denition1.
4.
1.
ForagraphG=(V(G),E(G)),thebinaryrelation1.
InthissubsectionweexaminehowagiventotalorderingτofV(G)isoftenusedtobreaktieswhen|Eligible|>1.
ThistechniquecanbeusedwithanygivengraphsearchSwherethe"+"versionisdenotedS+(τ).
Ina"+"sweepthevertextobechosenistherightmostEligiblevertexasorderedbyτasfollows:171.
GRAPHSEARCHINCOCOMPARABILITYGRAPHSThe+tie-breakrule:Initiallytherstvertexofσ=S+(τ)ischosentobetherightmostvertexofτ.
Thereafterif|Eligible|>1,thenthenextvertexofσistherightmostEligiblevertexasorderedbyτ.
Oneadvantageofthe"+"ruleisthatitmakestheoutputofasearchdeter-ministic.
GivenasearchS,agraphGandanorderingτ,thereexistsonlyoneorderingσsuchthatσ=S+(G,τ).
Usuallyτitselfisavertexorderingproducedbyagraphsearch.
Thistech-niquehasbeensuccessfullyusedwithLBFSwheretheinitialorderingisanar-bitraryLBFSandsubsequentLBFS+sweepsarethenemployed;forexample,torecognizeUnitIntervalgraphsanLBFSfollowedbytwoLBFS+sweepssuces[Cor04b],whereastorecognizeIntervalgraphsanLBFS,followedbyfourLBFS+sweeps,followedbyanLBFSthatqueriesthetwopreviousLBFS+sweepssuces[COS09].
1.
5.
2Graphsearchesthatmaintainacocomporderingwhenusedasa"+"sweepWerstpresentakeydenitionbasedonavertexhavingaprivateneighborwithrespecttoanothervertex.
Thisnotionplaysakeyroleindeterminingwhichsearchestransformagivencocomporderingintoococomporderingthatisalsothatspecicsearch.
Denition1.
5.
1.
Avertexy∈EligiblesatisesthePrivateNeighborProperty(PNP)withrespecttographsearchSifforeveryz∈VunvisitedEligible,withyz/∈E,thereexistsanx∈Xsuchthatxy∈Eandxz/∈E.
AsearchSsatisesthePrivateNeighborPropertyifateverystepofthesearch(i.
e.
,foreverysubsetXofvisitedvertices)everyvertexinEligiblesatisesthePNP.
Theorem1.
5.
2.
ForacocomparabilitygraphG=(V(G),E(G)),letτbeacocomporderingofG.
IfSisagraphsearchsatisfyingboththeGraphSearchParadigm1andthePrivateNeighborPropertythenσ=S+(G,τ)isalsoacocomp1InfactthesecondconditionoftheGSPisnotrequiredfortheproof.
181.
5Graphsearchincocomparabilitygraphsordering.
FurthermoreifτisalinearextensionofthepartialorderP=(V(G),≤),thenσisalinearextensionofP(wherePisthepartialorderobtainedfromPbyreversingallthearcs).
1Proof.
Toprovethistheorem,weneedtoprovethefollowingfact.
Claim1.
5.
3.
Foreveryuv/∈E(G),ugraphsearchsatisfyingthePNP,thereexistsatleastonevertexwsuchthat:wsearchesproduceacocomporderingwhenappliedasa"+"searchonagivencocompordering,weshowthatbymakingaslightadjustment,theabovetheoremcanbetransformedintoacharacterization.
Theorem1.
5.
4.
LetτbeacocomparabilityorderingoftheconnectedgraphGandletSbeasearchsatisfyingtheGraphSearchParadigm;further,letσ=S+(τ).
ThenσisacocomparabilityorderingifandonlyifatallstagesofS+(τ)therightmostvertexofEligiblesatisesthePNP.
1Thisfactisaneasyconsequenceofthedenitionsofthe+tie-breakruleandcocomporderingsandwillbeomittedinthesubsequentsimilarresults.
191.
GRAPHSEARCHINCOCOMPARABILITYGRAPHSProof.
()Thisfollowsfromtheprevioustheorem.
()Assumeσisacocomparabilityorder,butforsomeX,utherightmostvertexofEligibleinτdoesnotsatisfythePNPaswitnessedbyvertexv∈VunvisitedEligiblewhereuv/∈EandthereisnoxinXsuchthatxu∈E,xv/∈E.
Sinceu∈Eligibleandv∈VunvisitedEligible,bythelefttwincompatibleconditionweseethatN(u)∩X=N(v)∩X.
Thus,sinceudoesnothaveaprivateneighborinXwithrespecttov,vhasaprivateneighborw∈Xwithrespecttou.
Nowweseethatwsearchesproduceacocomporderingwhenappliedasa"+"searchonagivencocompordering.
Inlightoftheorem1.
5.
2,itsucestoshowthatanysearchthatsatisesconditions1and3oftheGSPalsosatisesthePNP;inlightoftheorem1.
5.
4itsucestoshowthatanysearchthatsatisestheGSPalsohasthelastvertexofeveryEligiblesatisfyingthePNP.
Thefollowinglemmashowsthatallsearchesmentionedinsection1.
3satisfytherequirementsoftheorem1.
5.
2.
Lemma1.
5.
5.
ForallSin{GENS,BFS,DFS,MNS,LBFS,LDFS,MCS},SsatisesboththeGraphSearchParadigmandthePrivateNeighborProperty.
Proof.
ItitclearfromtheirdenitionsthatallsearchessatisfytheGSP;wedealwithPNPsatisfactiononacasebycasebasis.
Forgenericsearch,sinceeveryvertexwithaneighborinXbelongstoEligible,theverticesinVunvisitedEligiblehavenoneighborinX.
ThereforegenericsearchsatisesthePNP.
Usingtheusualdatastructures:aqueue(respectivelyastack)forBFS(re-spectivelyDFS),onecanviewthesesearchesasselectingateverystep,(i.
e.
,foreverysetXVofvisitedvertices)Eligibleasthesetofunvisitedneighborsofsomevertexx∈X.
ThereforenovertexinVunvisitedEligibleisadjacenttoxandthusbothsearchessatisfythePNP.
ForallsearchesthatareMNSs(suchasLBFS,LDFS,MCS)forally∈Eligibleandforallz∈VunvisitedEligibleweknowthat(N(y)∩X)(N(z)∩X)201.
6Consequencesandthusforeverysuchy,zpair,yhasaprivateneighborinXwithrespecttoz.
Corollary1.
5.
6.
ForanycocomporderingτandanygraphsearchSin{GENS,BFS,DFS,MNS,LBFS,LDFS,MCS,RMN},σ=S+(τ)isalsoacocompordering.
Proof.
Thisfollowsimmediatelyfromtheorem1.
5.
2andlemma1.
5.
5.
1.
6ConsequencesUsingtheresultsoftheprevioussections,wenowhaveatool-boxtoproducecocomporderingswithparticularproperties(inheritedfromthesearchwehaveused).
WithourtoolboxwecanproducecocomporderingswhichareBFS(resp.
DFS,MNS,LDFSorLBFS)orderings.
Applicationsofthiswillbepresentedintherestofthethesis.
Itmustbenotedthatforourtoolboxtowork,weneedacocompordering.
Itisknownthatgivenacocomparabilitygraph,acocomporderingcanbecomputedinlineartime[MS99].
ButthisalgorithmisquiteinvolvedandotheralgorithmsinO(n+mlogn)areeasiertohandle[HMPV00,MS99].
AnewalgorithmforndingacocomporderingusingonlyLBFS+willbepresentedinthisthesisinchapter5.
Itshouldalsobenoticedthatourtoolboxcanbeeasilyextendedtomin-LBFSasdenedin[Mei05].
Sofar,inthethirdsectionwehaveintroducedintervalgraphandintervalorderingsbutwedonottalkabouttheminthetoolbox.
Thereasonisthatanintervalorderingisalreadya{GENS,BFS,DFS,MNS,LBFS,LDFS,MCS,RMN}ordering.
211.
GRAPHSEARCHINCOCOMPARABILITYGRAPHS222AnewcharacterizationtheoremforCocomparabilityGraphs2.
1IntroductionThischapterisdedicatedtoanewcharacterizationtheoremforcocomparabilitygraphs.
Thistheoremstatesthatthesetofmaximalcliquesofacocomparabilitycanbeequippedwithalatticestructurerespectingsomeproperties.
Thistheoremcanbeseenasageneralizationofatheoremforintervalgraphs.
Thischapterisorganizedasfollows.
Insection2.
2,weintroducesometer-minologiesandreviewthemainresultsaboutthemaximalantichainlatticeofapartialorderthatweneedfortheproof.
Insection2.
3weprovesomeadditionalpropertiesaboutthismaximalantichainlattice.
Section2.
4isdevotedtotheproofofthenewcharacterizationtheorem.
ThisworkhasbeendoneincollaborationwithMichelHabib.
2.
2Themaximalantichainlatticeofapartialorder(MA(P))FromapartialorderP,wecanbuilddierentlatticesliketheAntichainlattice,theMaximalSizedAntichainLattice.
.
.
Oneofthemisthelatticeofmaximalantichains.
Asprovedin[B.
88],thesetofmaximal(underinclusion)antichainsofagivenpartialorderPdenotedbyMAP(P),formsalatticewhenequipped232.
ANEWCHARACTERIZATIONTHEOREMFORCOCOMPARABILITYGRAPHSwiththefollowingbinaryrelation≤MA(P):ForA,B∈MAP(P),A≤MA(P)Bifandonlyify∈B,x∈Asuchthatx≤Py.
WedenotethislatticebyMA(P)=(MAP(P),≤MA(P)).
InthissectionweintroducesometerminologyandreviewthemainresultsknownaboutMA(P)=(MAP(P),≤MA(P)),whichinterestus.
Theorem2.
2.
1.
[B.
88]LetPbeapartialorder.
MA(P)=(MAP(P),≤MA(P))isapartialorder.
Thenextlemmashowthatthedenitionisself-dual.
Lemma2.
2.
2.
[B.
88]LetA,BbetwomaximalantichainsofapartialorderP.
A≤MA(P)Bifandonlyifx∈A,y∈Bwithx≤Py.
Wenowintroducesometerminologyandproveashortproposition.
FortwomaximalantichainsA,BofapartialorderP=(V(G),≤P),letS(A,B)={x∈AB|y∈BAwithxjSinceC0=,thehypothesisistruefortheinitialcase.
Assumethatthehypothesisistruefortherstj≥1cliques.
WhenwestarttobuildthecliqueCj+1,weaddavertexthathasnotbeenconsideredbeforeanditsneighborhoodthatbelongtoCj.
Bydoingso,wecannotaddavertexxtoCj+1suchthatx∈CiCjandigraphsofcorollary2.
4.
4,Chain-cliqueoutputsasequenceofcliquesthatdenesanintervalsubgraph.
383.
2SpanningintervalgraphsProposition3.
2.
3.
ForagraphGandanorderingσ,ChaincliqueoutputsasequenceofcliquesC=C1,CksuchthatσisanintervalorderingforGCandx∈CiCj,y∈CjCi,igraphformedbythesequenceisamaximalintervalsubgraphfortheordering.
Proposition3.
2.
4.
ForagraphGandanorderingσ,ChaincliqueoutputsasequenceofcliquesC=C1,Ckthatinducesamaximalintervalsubgraphfortheorderingσ.
Proof.
AssumeforcontradictionthatC=C1,Ckdoesnotformamaximalintervalsubgraphfortheorderingσ.
ThereforethereexistsanonemptysetofedgesSsuchthatσisanintervalorderingforthegraphH=(V(G),E(C)∪S).
LetuvbeanedgeofSandassumewithoutalossofgeneralitythatugraphH.
Proposition3.
2.
5.
ChaincliquehascomplexityO(n+m).
Proof.
Allthetestscanbeperformedbyenumeratingoncetheneighborhoodofavertex.
Sincethesequenceofcliquesformsasubgraph,itssizeisboundbym.
Therefore,ChaincliquehascomplexityO(n+m).
393.
INTERVALSUBGRAPHSOFCOCOMPARABILITYGRAPHS3.
3ComputingamaximalchainofMA(P)Inthissection,weintroduceanewgraphsearchthatwillhelpustocomputeamaximalchainofMA(P)inagreedyfashion.
ThisgraphsearchwillbebaptizedLocalMNSandwhenweuseChaincliqueonaLocalMNScocomporderingwegetamaximalchainofMA(P).
First,westartbylookingatthebehaviorofChaincliqueonaLBFSandaLDFSordering.
LetusconsiderthegraphinFigure3.
2.
ApplyingthealgorithmChaincliqueontheLDFSordering1,3,2,4,6,5,wegetthechain{1,2,3},{1,2,4}and{4,5,6}.
WegetthesameresultusingtheLBFSordering2,3,1,4,6,5.
Thus,LBFSandLDFSdoesnothelpustondamaximalchainofcliquesofMA(P)usingChaincliqueonthem.
SowenowintroduceLocalMNS(Algorithm5).
Figure3.
2:MA(P)andthecorrespondingcocomparabilitygraphG.
403.
3ComputingamaximalchainofMA(P)Algorithm5:LocalMNSData:G=(V,E)Result:atotalorderingσsuchthatσ(i)isthei'thvisitedvertexD1←;V←V%{Visthesetofunchosenvertices}%;X←;fori=1to|V|dovischosenasavertexwithmaximalneighborhoodinDi;σ(i)←v;V←V{v};X←X∪{v};Di+1←{v}∪(N(v)∩Di);endThisalgorithmisverysimilartotheMNSalgorithm.
TheonlydierenceisinLocalMNSweareconsideringtheneighborhoodoftheunvisitedverticesonlyinDi,whichcanbeastrictsubsetofX(theunvisitedvertices)andinthecaseofMNSweareconsideringtheneighborhoodinX.
ThisisthereasonforthenameLocalMNS.
LetuslookatthebehaviorofLocalMNS+onexample3.
2.
Letτ=5,6,4,2,3,1beacocompordering.
LocalMNS+(G,τ)=1,3,2,4,5,6isacocomporderingandChaincliquegivesthemaximalchain{1,2,3},{1,2,4},{1,4,5}and{4,5,6}.
WenowprovethatChaincliqueonaLocalMNScocomporderingoutputsamaximalchainofcliques.
LetGbeacocomparabilitygraphandτaco-comporderingofG.
Theproofisorganizedasfollows.
Werstshowthatσ=LocalMNS+(G,τ)isacocompordering.
ThenwedescribethestructureofamaximalchainofMA(Pσ)anditsrelationtoPσ.
FinallyweprovethatChainclique(G,σ)outputsamaximalchainofMA(Pσ).
Lemma3.
3.
1.
LocalMNSrespectsboththeGraphSearchParadigmandthePri-vateNeighborProperty.
Proof.
UsingitsdenitionitisclearthatLocalMNSsatisestheGSP.
Whenwe413.
INTERVALSUBGRAPHSOFCOCOMPARABILITYGRAPHSmakeourchoicetheelligibleverticesisthesetofverticeswithmaximalneigh-borhoodinDiandaswithothermaximalsearches,itrespectsthePNP.
Corollary3.
3.
2.
IfGisacocomparabilitygraph,τisacocomporderingandσ=LocalMNS+(G,τ)thenσisacocompordering.
Proof.
Becauseoflemma3.
3.
1,LocalMNSrespectsboththeGraphSearchParadigmandthePrivateNeighbourPropertyandsousingtheorem1.
5.
2,wededucethatσisacocompordering.
Theorem3.
3.
3.
LetGbeacocomparabilitygraphandletσbeacocompordering.
C11.
Wehavetwocases:σ(i)iscompletetoDiornot.
Intherstcase,LocalMNSincreasesthesetDibyaddingσ(i)andChaincliquewillincreasethecliqueCpi1ji1byaddingσ(i).
Thereforeusingtheinductionhypothesisatstepi,wededucethatDi+1=Cpiji.
Inthesecondcase,LocalMNSsetsDi+1=Di∩N(σ(i)).
Inthesameway,ChaincliquecreatesanewcliqueC1ji=Cpi1ji1∩N(σ(i)).
Thereforeusingtheinductionhypothesisatstepi,wededucethatDi+1=Cpiji.
Proposition3.
3.
5.
LetGbeacocomparabilitygraphandletτbeacocompordering.
Ifσ=LocalMNS+(G,τ)thenChainclique(G,σ)=C1,CkisachainofmaximalcliquesofMA(Pσ)suchthatC1MA(Pσ)Cbbeforeavertexx∈VCbandvistheleftmostsuchvertex.
LetCxbeamaximalcliquesuchthatx∈CxandCx≤MA(Pσ)Cb.
Wehavetwocases,eitherxv/∈Eorxv∈E.
Assumeweareintherstcase.
Usinglemma2.
3.
1onx,v,wededucethatxlast[v]}∪{last[v]}}.
Itmustbenotedthatforward[v]≥last[v].
ThevaluebackwardwillbetherstcliqueinwhichthevertexhasaneighbourinthegraphGbutnotintheintervalgraphandsowedenebackward[v]tobemin{{last[u]|u∈N(v)andlast[u]graphandσbeanMNScocomporderingoftheverticesofG.
Algorithm6outputsallthesimplicialverticesofG.
Proof.
Usingtheorem4.
2.
1wededucethatallthesimplicialverticesandtheirwholeneighbourhoodbelongtoonecliqueofthesequenceoutputbyChainclique.
584.
3SimplicialverticesincocomparabilitygraphsAlgorithm6:SimplicialverticesinacocomparabilitygraphData:G=(V(G),E(G))andanMNScocomporderingσofV(G)Result:ThesimplicialverticesofGComputethesequenceC1,.
.
.
,CkusingChainclique(G,σ);Computerst,last,backward,forwardforeveryvertexofV(G);S←%{Thesimplicialvertices}%;for(i←1ton)doifforward[σ(i)]==backward[σ(i)]thenS=S∪{σ(i)};endOutputS;Sototestifavertexisasimplicialvertex,wehavetocheckthatavertexbe-longstoonlyonecliqueinthesequenceandhasnoneighboursintherestoftheintervalgraph.
Becauseofourdenition,foranyvertexvwehavethatlast[v]≤forward[v]andbackward[v]≤first[v].
Soforanysimplicialvertexσ(i)wehavethatforward[σ(i)]==backward[σ(i)]==last[σ(i)]==first[σ(i)].
Ifavertexσ(i)isnotsimplicialtheneitheritbelongstomorethanonecliqueinthese-quenceandsolast[σ(i)]=first[σ(i)]implyingforward[σ(i)]=backward[σ(i)]orithasaneighboroutsidethesequenceandsolast[σ(i)]graph.
Theorem4.
3.
3.
Algorithm6hascomplexityO(n+m).
Proof.
ComputingaMNScocomporderingcanbedoneinO(n+m)usingLBFS+orMCS+(seechapter1).
ChainCliquehaveaspaceandtimecom-plexityO(n+m).
EnumeratethecliquesisinO(n+m).
Computingrstandlastcanbedonebyenumeratingallthecliquesofthespanningintervalgraph.
Thecomputationofforward,backwardcanbedonebyenumeratingforeachvertexitsneighbourhoodaftercomputingrstandlastansocanbedoneinO(n+m).
EnumeratingtheverticescanbedoneinO(n).
594.
SIMPLICIALVERTICESANDCLIQUESEPARATORSINCOCOMPARABILITYGRAPHS4.
4Minimalcliqueseparatorsincocomparabil-itygraphsThissectionisorganizedasfollows.
Intherstsubsection,wepresenttheproblemofndingminimalcliqueseparatorsandouralgorithm.
Thesecondsubsectionisdevotedtoprovesomeresultsaboutcliqueseparatorsincocomparabilitygraphs.
Thethirdsubsectionisdevotedtothestudyofthestructureoftheatomsofacocomparabilitygraph.
Thelastsubsectionisdevotedtothecorrectnessofthealgorithm.
4.
4.
1TheproblemofminimalcliqueseparatorsWerecallthatforaconnectedgraphG,SV(G)isaseparatorifGSisdisconnected.
Fortwoverticesa,b∈V(G),Sisanab-separatorifaandbareindierentconnectedcomponentsofGS.
Sisaminimalab-separatorifnopropersubsetofSisanab-separator.
SisaminimalcliqueseparatorofagraphGifSisacliqueandthereissomevertexa,bsuchthatSisaminimalab-separator.
Anatomisamaximalinducedsubgraphthatadmitsnocliqueseparator.
Traditionallythedecompositionispresentedusingatree.
Eachnodeisacliqueseparatorandtheleavesformedtheconnectedcomponents.
Forthedecom-positiontobeunique,thecliqueseparatorsmustbeminimalcliqueseparators.
Foranexample,seeFigure4.
2.
Figure4.
2:AgraphGanditsdecompositiontreeusingminimalcliqueseparators.
Inthetreedecomposition,theatomsareexactlytheleavesofthetree.
ThereisalwaysatmostnatomsandthesizeofthedecompositionisinO(n+m)(see604.
4Minimalcliqueseparatorsincocomparabilitygraphs[BPS10]).
Ouralgorithmtodecomposeacocomparabilitygraphusingitscliquesepara-torsdoesnotoutputthetreedecomposition.
Butinstead,itoutputsthelistoftheatomsofthegraph:A1,AlsuchthatAa∩AcAbfor1≤a≤b≤c≤landAa∩Abisaclique.
Theadvantageisitissimplertohandlethanatreedecompositionbutstillallowsustousethedivideandconquerstrategytosolveaproblem.
Togetthecliqueseparators,wejusthavetocomputetheintersectionoftwoconsecutiveatomsinthelist.
Forexample,forthecoloringproblemthealgorithmis:Algorithm7:DivideandconquerData:TheatomsA1,AlsuchthatAa∩AcAbfor1≤a≤b≤c≤landAa∩AbisacliqueResult:Anoptimalcoloringi←1;whilei≤ldoFindanoptimalcoloringforAi;Joinittothecurrentcoloring;i←i+1;endOutputthecoloring;Thecorrectnessofthisalgorithmreliesontheintervalstructureoftheatoms.
WeknowthattheintersectionoftwoatomsformsacliqueandthatAa∩AcAbfor1≤a≤b≤c≤l.
Intervalgraphshavethesamestructureandsotheproofisthesameasforintervalgraphs,exceptthattheatomsarecompletegraphsinthecaseofintervalgraphs.
Sinceweassumethatwehaveaproceduretoperfectlycomputeanoptimalcoloringofanatom,thealgorithmwillouputanoptimalcoloringofthegraph.
Thesamekindofalgorithmworksforthemaximumcliqueproblemandtheminimumll-in.
Forthemaximumindependentset,incocomparabilitygraphs614.
SIMPLICIALVERTICESANDCLIQUESEPARATORSINCOCOMPARABILITYGRAPHSthecliquedecompositiondoesnothelpmuchsinceagreedyalgorithmonaspecialcocomporderingworks(see[CDHK]).
Wenowpresentthealgorithmtocomputeadecompositionofcocomparabilitygraphsusingcliqueseparator(Algorithm8).
Thecorrectnessofthealgorithmwillmainlyrelyontheorem4.
4.
7,theorem4.
4.
8andtheorem4.
2.
1.
Asforthesimplicialvertices,wewillalsocomputerst,last,backwardandforward.
CiawillbethesetofverticesthatappearorhavesomeneighborthatappearsbeforethecliqueCiintheintervalgraphandCibwillbethesetofverticesthatappearorhaveaneighborthatappearsafterthecliqueCiintheintervalgraph.
Foranexample,letusconsiderthegraphinFigure4.
3.
σ=v1,v2,v3,v4,v6,v5,v7,v9,v8isaLBFScocompordering.
Chaincliqueoutputs{v1,v2,v3},{v2,v4},{v2,v6},{v5,v6,v7},{v6,v9},{v9,v8}.
Algorithm8willoutput{v1,v2,v3},{v2,v3,v4,v5,v6},{v5,v6,v7}and{v5,v6,v8,v9}.
Figure4.
3:Acocomparabilitygraphanditslattice.
4.
4.
2Cliqueseparatorsandcomponentsincocomparabil-itygraphsThissubsectionisorganizedasfollows.
First,werecallawell-knownpropositionandintroducesometerminology,thenweprovesomeclaims,lemmaandtheoremonthestructureofthecliqueseparatorsincocomparabilitygraphs.
624.
4MinimalcliqueseparatorsincocomparabilitygraphsAlgorithm8:ListofatomsData:aconnectedgraphG=(V(G),E(G))andaMNScocomporderingτofV(G)Result:AsequenceoftheatomsofGC1,Ck=Chainclique(G,τ);Computerst,last,backward,forwardforeveryvertexofV;LetL=%{Thesequenceoftheatoms}%;LetDis←;LetA←;for(i←1tok)doif(x∈Disandforward[x]>i)thenLetCia←{u∈Ci|first[u]iorforward[u]>i};ifCia=and(ACia)thenAppend(A∪Cia)toL;endif(CiCia=andCiCib=)thenAppend(Ci)toL;endA←Cib;elseA←A∪{v∈Ci|last[v]=i};endDis←Dis∪{u∈Ci|last[u]=i};endOutputL;Proposition4.
4.
1.
LetGbeagraph.
SisaminimalseparatorfortwoconnectedcomponentsD1,D2ofGSifandonlyifx∈S,N(x)∩D1=andN(x)∩D2=.
LetGbeacocomparabilitygraphandσacocompordering.
ForamaximalcliqueA,letusdenotebyBELOW(A)={x∈V|thereexistsamaximalcliqueCx,x∈CxandCxi.
Proof.
LetusassumethatCiisnotamaximalclique;letvbetherstvertexofCiCi1inσ.
704.
4MinimalcliqueseparatorsincocomparabilitygraphsIfitexists,letwbetherightmostvertexcompletetoCi,w/∈Ciandwi.
Proof.
FortheforwarddirectionassumethatCiadmitsanincomparableclique.
LetDbeacliquesuchthatDMA(Pσ)Ci.
SinceDMA(Pσ)Ci,S(D,Ci)=andS+(D,Ci)=otherwisefromthedenitionof∨MA(Pσ)and∧MA(Pσ)wededucethateitherDD∨MA(Pσ)CiorDD∧MA(Pσ)Ci,thereforecontradictingthemaximalityofDorDMA(Pσ)Ci.
Letu∈S(D,Ci)andv∈S+(D,Ci).
Sinceu∈S(D,Ci),thereexistsx∈Cisuchthatui.
Forthereversedirectionassumethereexistsu,vsuchthatuv∈E,last[u]i.
Letusprovethatsincelast[u]i.
Sothiscasecan'thappen.
Inthesecondcase,sinceu∈Cuv,u∈Cu,proposition2.
3.
3impliesthatu∈Ciwhichcontradictsthatlast[u]graphandσaMNScocomporderingoftheverticesofG.
Algorithm8outputsalltheatomsofGandhascomplexityinO(n+m).
Proof.
Theorem4.
2.
1guaranteesthatanyfullyincomparablecliquewillbelongtoC1,.
.
.
,Ck.
Thetwoclaims4.
4.
10and4.
4.
9conrmthatouralgorithmwilldetectwhenacliqueisfullycomparable.
Theorem4.
4.
8certiesthatifGhasaatomwhichisaclique,thenthisatomwillbefoundbythealgorithm.
Theorem4.
4.
7certiesthatifGhasaatomwhichisnotacliquethentheatomwillbefoundbythealgorithm.
ComputingaMNScocomporderingcanbedoneinO(n+m)usingforex-ampleLBFS+(G,σ)whereσisacocomporder.
TheChainCliquealgorithmhascomplexityO(n+m).
EnumeratingallthecliquescanbedoneinO(n+m).
Com-putingrstandlastcanbedonebyenumeratingallthecliquesofthespanningintervalgraph.
Thecomputationofforward,backwardcanbedonebyenumer-atingforeachvertexitsneighbourhoodaftercomputingrstandlastandsocanbedoneinO(n+m).
Toverifythatx∈Disandforward[x]>i,wejusthavetokeepthex∈Dissuchthaty∈Dis,forward[x]≥forward[y]andsocanbedoneeasily.
Nowateachstep,wecaneasilycheckalltheconditionsinO(Ci).
724.
5ConclusionsandperspectivesforfurtherworkThereforethealgorithmhascomplexityO(n+m).
4.
5ConclusionsandperspectivesforfurtherworkThemostinterestingresultofthissectionisthatwehaveanewwaytodecomposeapartialorder.
Thisdecompositioncanbefoundecientlyandhasgoodalgo-rithmicperspectives.
Oneinterestingapplicationistondanoptimalcoloringforcocomparabilitygraphs.
Sofarthebestalgorithmusematrixmultiplication.
Wecanaskthatifweusethecliqueseparatorsasapreliminariesstep,whataretheconsequencesontheproblemofcoloringcocomparabilitygraphsThemainproblemisthatacocomparabilitygraphmaynothaveacliqueseparator(forexamplecompletebipartitegraphs).
Soitraiseslotofcombinatoricquestions:WhatistheprobabilityofhavingacliqueseparatorGivenapartialorder,whatisthemaximumsizeofanatomAnotherwaytouseitistodenenewgraphclasses;forexampleacocompara-bilitygraphwhoseatomsareallcobipartitegraphs.
Thisclasscanberecognizedinlineartimeusingouralgorithmtondthedecompositionandthentestifeachatomisacobipartitegraph.
Forthisclass,wedonotevenneedthedecompo-sitionalgorithmandcanusethefullycomparableclique,testingifbetweentwofullycomparablecliquesthegraphformsacobipartitegraph.
734.
SIMPLICIALVERTICESANDCLIQUESEPARATORSINCOCOMPARABILITYGRAPHS745TransitiveOrientation:MultisweepLBFS5.
1IntroductionInthischapter,wepresentanalgorithmtondacocompordering.
Therefore,itcanalsobeseenasanalgorithmtondatransitiveorientation.
Therealreadyexistsseveralalgorithmstondaco-umbrellafreeorderingofacomparabilitygraph,includingalineartimeonedescribedin[MS99]butitisquiteinvolved.
ThereexistsalsoalgorithmswithrunningtimeO(n+mlogn)liketheonepre-sentedin[HMPV00],whichareeasiertohandle.
Itshouldbenoticedthatthesealgorithmsdonotprovideafast(i.
e.
linear)waytorecognizecomparabilitygraphsandcocomparabilitygraphs.
Theclassicstrategytorecognizeacocom-parability(resp.
comparability)graphisbyusingrstanalgorithmtondaumbrella(resp.
co-umbrella)freeorderingandthencheckifthisorderingisum-brella(resp.
co-umbrella)free.
Uptonow,itisstillunknownifwecanperformthistestingoperationinlineartime.
Sofarthebestalgorithmfortestingthisorderingusesbooleanmatrixmultiplication[Spi03].
ThealgorithmwepresentinthischapteronlyusesLBFS+.
Intheworstcase,itperformsnLBFS+.
Thiskindofalgorithmisoftenreferredasamultisweepalgorithm.
Thisalgorithmanswerspositivelyaquestionaskedin[COS09],namely:whetherthereexistsamultisweepalgorithmbasedonLBFStondacocomporderingofacocomparabilitygraph.
ThisalgorithmhasrunningtimeO(nm)andevenifthealgorithmisslowerthantheonein[MS99],fortheproblemofrecognitionitwillperformaswellastheotheroneswithcomplexitylessthan755.
TRANSITIVEORIENTATION:MULTISWEEPLBFSO(nm).
Thestrongpointofthisalgorithmliesinitssimplicity.
Furthermore,thisalgorithmgivessomehopefortheexistenceofasimplemultisweep"LBFS"basedalgorithmwithlinearrunningtimetotransitivelyorientcomparabilitygraphs(see5.
4.
1).
Thischapterisorganizedasfollows.
Insection5.
2,wepresentthealgorithm.
Section5.
3isdevotedtothecorrectnessofthealgorithm.
Section5.
4containsconclusionandsomeconjectures.
ThisworkhasbeendoneincollaborationwithMichelHabibandsubmitted[DH].
5.
2SeriesofLBFSLetusstartbyintroducingtheRepeatedLBFS+algorithmwhichisthemainalgorithmstudiedinthischapter.
Algorithm9:RepeatedLBFS+Data:G=(V(G),E(G))anundirectedgraphResult:anorderingσn1σ1←LBFS(G);2fori=2to|V(G)|do3σi←LBFS+(G,σi1);4end5Outputσ|V(G)|;LetusillustratethebehaviourofRepeatedLBFS+withthegraphongure5.
1.
Therstordering,σ1willbeforexampleσ1=.
Thereforeσ2=,σ3=,σ4=,σ5==σ3,σ6==σ4.
Itiseasytocheckthatσ3andσ4havenoumbrella.
Thischapterisdevotedtoaproofofthefollowingresult:Mainresult:GisacocomparabilitygraphifandonlyifRepeatedLBFS+computesacocompordering.
765.
3ProofofRepeatedLBFS+AlgorithmFigure5.
1:AcocomparabilitygraphG=(V(G),E(G))Thefollowingresulthasalreadybeenprovedforintervalgraphsbuthasnotbeenpublished.
Theorem5.
2.
1.
[CK]G=(V(G),E(G))isanintervalgraphifandonlyifRepeatedLBFS+computesanintervalordering.
Wenowgeneralizeithereforthewiderclassofcocomparabilitygraphs.
Incorollary5.
3.
16,wewillshowthattheprevioustheoremisacorollaryofourresult.
Sinceunfortunatelythereareexamplesonwhichtheconvergencedependsonthenumberofvertices,see[Ma,COS09],Repeated+cannotuseaconstantnumberofLBFS+.
TheuseofLBFSisalsomotivatedbythetwofollowingresults.
Theorem5.
2.
2.
[HMPV00]LetsbethelastvertexvisitedbyaLBFSonaco-comparabilitygraphG;thenthereexistsacocomporderingstarting(resp.
ending)ats.
ThereforethelastvertexofaLBFSinacocomparabilitygraphcanbetakenasthestartingpointofacocomporderingandsothesetworesultsgiveussomehopethataseriesofsuccessiveLBFS+producesacocompordering.
5.
3ProofofRepeatedLBFS+Algorithm5.
3.
1SketchoftheproofofourmainresultOurproofthatRepeatedLBFS+computesacocomporderingisquiteinvolvedandasalreadymentionedtheyarenotsomanytoolstoanalyzemultisweepalgo-775.
TRANSITIVEORIENTATION:MULTISWEEPLBFSrithms.
WeproposeanalgorithmicproofbyintroducingacompanionalgorithmPartitionalgorithmtoLBFS+,andstudyingtheircommoninvariantsinordertoprovethattheybothproduceacocompordering(notnecessarilythesameone).
Thisrequiresparticularnotationanddenitionswhichareintroducedinthenextsubsection.
5.
3.
2DenitionsandnotationsLetX=beanorderedpartitionofV(G),inwhichX(j)denotesthejthpartofthepartitionX.
|X|denotesthenumberofpartsofthepartitionX.
LetXdenotethereverseorderedpartitionofXandapartofXisthereforedenedbyX(i)=X(|X|i+1).
Foravertexx∈X(j),wedeneitsleftneighborhoodasLN(x,X)={y∈N(x)|y∈X(k)andkgraph.
WewillsaythatXisleft-modularifandonlyifj,1≤j≤|X|,ifx,y∈X(j)thenLN(x,X)=LN(y,X).
Denition5.
3.
2.
LetXbeanorderedpartitionoftheverticesofGacocompa-rabilitygraph.
WewillsaythatXiscompatiblewithanorderingτifandonlyifx∈X(j),y∈X(k),jgraph.
WewillsaythatXisacocomporderedpartitionifandonlyifXiscompatiblewithacocompordering.
5.
3.
3TheproofLetusstartbyprovingsomepropositionsaboutcocomporderedpartitions.
785.
3ProofofRepeatedLBFS+AlgorithmProposition5.
3.
4.
LetG=(V(G),E(G))beacocomparabilitygraphandXbeacocomporderedpartitionofV(G).
Ifx,y∈X(j),xy/∈E(G)thenLN(x,X)LN(y,X)orLN(y,X)LN(x,X).
Proof.
Assumeforcontradictionthatthereexistsx,y∈X(j)suchthatxy/∈E(G),LN(x,X)LN(y,X)andLN(y,X)LN(x,X).
SinceXisacocomporderedpartition,letτbeacocomporderingsuchthatXiscompatiblewithτ.
Wenowhavetwocases:eitherygraph,letσi1beaLBFSofGandletσi=LBFS+(G,σi1).
IfXi1isacocompleft-modularorderedpartitioncompatiblewithσi1,thenXi1isacocomporderedpartitioncompatiblewithσi.
Proof.
AssumeforcontradictionthatXi1isnotcompatiblewithσi.
Soweknowthatthereexistsacounter-examplei.
e.
twoverticesx∈Xi1(j)andy∈Xi1(k)suchthat:jlabely(x).
Thereforeyhasaprivateneighbourusuchthatugraph,letσbeaLBFSofGandXbealeft-modularorderedpartitioncompatiblewithσ.
ThentherestrictionofσtoapartX(i)isalegitimateLBFSorderingofG(X(i)).
795.
TRANSITIVEORIENTATION:MULTISWEEPLBFSProof.
AssumeforcontradictionthattherestrictionofσtoapartX(i)ofthepartitionXisnotanLBFSordering.
Thereforeusingtheorem1.
3.
4onσ,wededucethatthereexiststhreeverticesa,b,c∈X(i)suchthatac∈E(G),ab/∈E(G),a,σ2=,σ3=,σ4=,σ5=,σ6=.
Bycon-ventionwesetX1=.
InthisexamplewehaveX1=.
TobuildX2,theinputisσ2,X1.
SofortherstpartofX2weputtheleftmostvertex805.
3ProofofRepeatedLBFS+AlgorithmAlgorithm10:PartitionData:AvertexorderingσiandapartitionXi1ofV(G)Result:AnorderedpartitionXi=Partition(Xi1,σi)1XiInitializationofthenewpartition}%2l←1;%{Xi(l)denotesthepartofXithatwearebuilding}%3for(j←|Xi1|downto1)do4T(i,j)1←Xi1(j);%{T(i,j)1isthesetofverticesnotalreadyputsinXi}%5fi(j)←l%{indexoftherstpartusingtheverticesofXi1(j)}%;6k←1;7while(T(i,j)k=)do8LetxbetheleftmostvertexofT(i,j)kinσi;9if(Xi1(j)=T(i,j)kthen10Xi(l)←{x};11else12Xi(l)←{u∈T(i,j)k|LN(x,Xi)=LN(u,Xi)}%{Putinthenewpartalltheverticeswiththesameleftneigborhoodthanx}%;13end14T(i,j)k+1←T(i,j)kXi(l);15k←k+1;16l←l+1;17end18gi(j)←l%{indexofthelastpartusingtheverticesofXi1(j)}%;19j←j+1;20endinσ2whichise.
Inthesecondpartwewillputfandalltheverticeswithesameneighbourhood,thereforethesecondpartwillbeequalto{f,b}.
Andwecon-tinuelikethat.
AttheendwendX2=.
ForX3thealgorithmwilloutputthepartition.
ItmustbenoticedthatifthepartitionXi1isthetrivialpartition(madeupwithsingletons),thenthealgorithmoutputsXi=Xi1.
SothealgorithmwilloutputthepartitionX4=,X5==X3815.
TRANSITIVEORIENTATION:MULTISWEEPLBFSandX6==X4.
Itshouldbenoticedthatσ3andX3(resp.
σ4andX4)donotprovidethesameorderingoftheverticesofG,butσ3andX3(resp.
σ4andX4)arenotonlybothcocomporderingsbutalsolinearextensionsofthesametransitiveorientationofG.
Firsttwoeasyobservations:Proposition5.
3.
7.
ForeverypartitionXi1andeveryorderingσi,Xi=Partition(Xi1,σi)isleft-modular.
Proof.
EachtimeapartXi(j)ofXiisbuilt,weonlyputtogetherinXi(j)thesetofvertices{u∈T(j)k|LN(x,Xi1)=LN(u,Xi1)}init.
ThereforethenewpartitionXiisleft-modular.
Proposition5.
3.
8.
ForeverypartitionXi1andeveryorderingσi,Xi=Partition(Xi1,σi)isanorderedrenementofXi1.
Proof.
ApartofXi1canonlyberenedduringthePartitionalgorithm.
Fur-thermoreifXi1(i)andXi1(j)aretwopartsofXi1,withifor1≤j≤|Xi1|,1≤k≤gi(j)fi(j).
ThisseriesofpartitionsP(i,j)kdescribeshowthepartXi1(j)isdividedintopartsofthepartitionXi,asdescribedinFigure5.
3.
P(i,j)kisexactlythecurrentpartitionofXiatstep18ofthePartitionalgorithm.
Figure5.
3:IllustrationofthenotationdenedforthePartitionalgorithmTheorem5.
3.
9.
LetGbeacocomparabilitygraphandletσ1,.
.
.
,σnbetheseriesofLBFSorderingsproducedbyRepeatedLBFS+andX1,.
.
.
,XnbetheseriesoforderedpartitionssuchthatX1=andXi=Partition(Xi1,σi)for1.
Theproofisbyinductiononi.
Asinductionhypothesisweusethemaincommoninvariantsofthetwoalgorithms:(1)Xiisacocomporderedpartitioncompatiblewithσi.
(2)forallx,y∈Xi1(j),x∈Xi(p),y∈Xi(q),p,itisclearthatX1iscompatiblewithσ1.
SinceGisacocomparabilitygraph,thereexistsacocomporderingτandsinceX1=,X1iscompatiblewithτ.
SoX1isacocomporderedpartition.
For(2),sincewedeneX0=andX1=,(2)istriviallytrueattherststep.
Thereforetheinductionhypothesis(1)and(2)aretruefori=1.
Fortheinductionstep,supposethatthehypotheses(1)and(2)aretrueforeverylsuchthat1≤llabely(y).
ThereforeityieldsugraphinducedbytheverticesofSysuchthatyisanextremityofit.
SinceXi1iscocomp,left-modularandcompatiblewithσi1,usingtheorem5.
3.
6onXi1,weknowthattherestrictionofσi1toXi1(j)isanLBFSorderingforthegraphinducedbytheverticesofXi1.
SinceatthetimeyhasbeenchoseninσialltheverticesofSyhadthesamelabel,bythe+rulewededucethatywasthelastoftheverticesofSy.
Thereforeusingtheorem5.
2.
2,wededucethatforthesubgraphinducedbythesetofvertices{z|z∈Xi1(j)andzgraphinducedbySy,thereexistsacocomporderinginwhichyislast.
Sofar,weprovedthestartingcase.
Letusnowprovetheinductivestepwith855.
TRANSITIVEORIENTATION:MULTISWEEPLBFSthetwonextclaims.
Claim5.
3.
11.
Iftheinductionhypothesis(1)istruefori1andthehypothesis(i),(ii)aretruefork1,thenthehypotheses(i)istruefork.
Proof.
LetybetheleftmostvertexofT(i,j)kT(i,j)k+1withrespecttoσi.
SinceP(i,j)k1isacocomporderedpartition,letτbeacocomporderingsuchthatP(i,j)k1iscompatiblewithτ.
AssumeforcontradictionthatP(i,j)kisnotacocomporderedpartition.
ThereforeP(i,j)kisnotcompatiblewithτandthereexistsv∈T(i,j)k+1,u∈T(i,j)kT(i,j)k+1,uv/∈E(G),vlabely(y).
Thereforeityieldsvlabely(v).
Since865.
3ProofofRepeatedLBFS+AlgorithmLN(y,P(i,j)k1)=LN(u,P(i,j)k1),wemustalsohavelabely(u)>labely(v).
ThereforetheLBFSmustvisitubeforevinσiwhichcontradictsourchoiceofu,v.
Inthesecondcase,supposethatthereexistsw∈LN(u,P(i,j)k1)LN(v,P(i,j)k1)suchthatwlabely(v)andsolabely(u)>labely(v).
ThereforetheLBFSmustvisitubeforevinσiwhichcontradictsourchoiceofu,v.
Thereforeassumeforcontradictionthatw∈LN(u,P(i,j)k1)LN(v,P(i,j)k1)suchthatwlabely(x).
Letz∈N(y)N(x)besuchthatzgraphifandonlyiftheRepeatedLBFS+algorithmcomputesacocomporderinginatmost|V(G)|LBFS+.
Proof.
SupposethatRepeatedLBFS+algorithmcomputesacocomporderinginatmost|V(G)|LBFS+.
HenceGisacocomparabilitygraph.
Conversely,supposeGacocomparabilitygraph.
First,wewillprovethatinXn,ifeachpartcontainsonlyonevertex,thenthatσnisacocompordering.
Wedotheproofbyinductionandasaninvariantweshowthatatstepi,1≤i≤nthereexistsatleastinonemptypartsinthepartitionXi.
Fortheinitialstep,sinceX1=theinductionhypothesisistrue.
Fortheinductivestep,sinceforeachpartXi1(j)wecreateinXiapartthatcontainstheleftmostvertexofXiwithrespecttoσi,moreovereverypartthat885.
3ProofofRepeatedLBFS+Algorithmcontainsatleasttwoverticesisdivided.
Thereforeifthereisapartthatcontainstwoverticesthentheinductionhypothesisistrue.
IfeverypartcontainsonlyonevertexinXi1,wededucethatwehavenpartsinXi1.
Thereby,sincei≤n,theinductionhypothesisisalsotrue.
Assumeforcontradictionthatσnisnotacocompordering.
Thusthereexistsanumbrellau,v,w,suchthatugraphsandofwellknowntheoremaboutLBFSinchordalgraph.
Theorem5.
3.
14.
[RTL76]AgraphG=(V(G),E(G))isachordalgraphifandonlyifandonlyifthereexistsanorderingτofitsverticessuchthatforeverytripleofverticesa,b,csuchthatagraphGisachordalgraphifandonlyifLBFSproducesaperfecteliminationordering.
Nowitisnoweasytoprovethefollowingone:Theorem5.
3.
16.
GisanintervalgraphifandonlyifRepeatedLBFS+algorithmcomputesanintervalorderinginatmost|V(G)|LBFS+.
895.
TRANSITIVEORIENTATION:MULTISWEEPLBFSProof.
LetGbeanintervalgraph.
Usingtheorem1.
4.
8onG,wededucethatGisachordalgraphandacocomparabilitygraph.
SinceGisachordalgraphandσnisaLBFSorderingoftheverticesofG,wededuceusingtheorem5.
3.
15thatσnisaperfecteliminationordering.
Usingtheprevioustheorem,weknowthatσnisalsoacocompordering.
Letnowshowthatσnisanintervalordering.
Letusconsidera,b,csuchthatac∈E(G)andagraph.
Theorem5.
3.
17.
RepeatedLBFS+hascomplexityO(nm).
Proof.
ThedescriptionofalineartimeimplementationofLBFScanbefoundin[RTL76,HMPV00].
AlineartimeimplementationofLBFS+hasbeenexplainedin[COS09,Cor04b].
ThereforetheRepeatedLBFS+canbeimplementedinO(nm).
Sinceitiswell-known(seeforexample[HMPV00])thatgivenGandusingpartitionrenementaLBFScanbecomputedonGinlineartimeinthesizeofG,thisimmediatelyyieldsaverysimplealgorithmeasytoimplementthatcomputesinO(nm)atransitiveorientationofacomparabilitygraph.
Corollary5.
3.
18.
GisacomparabilitygraphifandonlyifRepeatedLBFS+algorithmappliedonGprovidesalinearextensionofatransitiveorientationofGinatmost|V(G)|LBFS+.
5.
4ConclusionsandperspectivesforfurtherworkInthischapterwehavepresentedandprovedanalgorithmbasedonaseriesofLBFS+tondacocomporderingifGisacocomparabilitygraph.
Thisanswersaquestionaskedin[COS09]abouttheexistenceofamultisweepLBFSalgorithmtondacocompordering.
Asabyproductthisalgorithmalsoworksforinterval905.
4Conclusionsandperspectivesforfurtherworkgraphsandthereforeweprovedaresultclaimedin[Ma,CK]butneverpublished.
Althoughtheworstcasecanbeachieved,wethinkthatinasimilarwaythatforintervalgraphsin[COS09],usinganextravariantofLBFSthefollowingcanbetrue.
Conjecture5.
4.
1.
IfGisacocomparabilitygraphthenaseriesofO(1)LBFS+followedbyaspecialLBFSalwaysproducesacocomporderinginO(n+m).
DuringourexperimentationofRepeatedLBFS+algorithm,formanygraphstheseriesoforderingfallsintoaloopofsize2,mostlyafterfewsteps.
Thereforeanaturalquestionis:ForaninniteseriesofLBFS+,whatisthesizeofthenalloopWeprovethatafteratmostnstepsthisseriesreachesthesetofcocomporderingsandusingcorollary1.
5.
6theseriesstaysincocomporderings.
Sincethenumberofcocomporderingsofagivengraphisnite,thisseriesnecessarilyfallintoanitecycle.
Conjecture5.
4.
2.
Thisloopisalwaysofsize2.
InotherwordstheseriesoforderingsoftheRepeatedLBFS+algorithmalwaysreachesacocomporderingafterwhichtheseriesalternatesbetweentwococomporderings.
Algorithm11:TransitiveorientationAlgorithmData:G=(V(G),E(G))aconnectedgraphResult:acocomporderingofGifandonlyifGisacocomparabilitygraph1σ1←LBFS(G);2σ2←LBFS+(G,σ1);3σ3←LBFS+(G,σ2);4i←3;5whileσi=σi2do6i←i+1;7σi←LBFS+(G,σi1);8end9Outputσi;915.
TRANSITIVEORIENTATION:MULTISWEEPLBFSIfconjecture5.
4.
2istrue,theabovealgorithmalwaysterminatesiftheinputisacomparabilitygraphinO(nm),anduptoourexperimentationsitseemstobelinearinaverageandthereforeverypractical.
926TBLS:anewmodelforgraphsearch6.
1IntroductionSomerecentapplicationsofgraphsearchesinvolveacontrolledtie-breakmecha-nisminaseriesofconsecutivegraphsearches,see[Cor04b,COS09,CDH13,DH].
Examplescanbefoundinthisthesisbutalsoincludethestronglyconnectedcomponentscomputationusingdouble-DFS[Sha81]andtheseriesofanarbitraryLBFSfollowedbytwoLBFS+susedtorecognizeunitintervalgraphs[Cor04b].
Thismotivatesageneralstudyofthesegraphsearchesequippedwithatie-breakmechanismthatincorporatessuchmulti-sweepusageofgraphsearches.
Thisisthegoalofthepresentchapter:todeneaframeworkpowerfulenoughtocap-turemanygraphsearcheseitherusedindividuallyorinamulti-sweepfashionandsimpleenoughtoallowgeneraltheoremsongraphsearches.
BuildingontheGeneralLabelSearch(GLS)frameworkfrom[KSB11]wenotonlysimplifytheirmodelbutalsounifytheirmodelwiththe"pattern-conditions"formalismof[CK08].
Theframeworkofthischapterismorerestrictedthantheonepresentedinchapter1butisinterestingsincemostoftheclassicalgraphsearchestinitanditallowustoexhibitanalgebraicstructure.
Thischapterisorganizedasfollows.
Section6.
2introducestheTie-BreakingLabelSearch(TBLS)formalismtoaddressgraphsearches.
WethenillustratetheTBLSbyexpressingsomeclassicalgraphsearchesinthisformalism.
Wewillalsoshowtherelationshipbetweenourformalismandthe"pattern-conditions"ofsearchorderingsintroducedin[CK08]therebyyieldingsomenewpattern-936.
TBLS:ANEWMODELFORGRAPHSEARCHconditionsforvariousclassicalsearches.
InSection6.
4weintroducetwonewgraphsearches.
InSection6.
5welookattherelationbetweenvariousclassicalgraphsearchesaswellasthetwonewsearches.
InSection6.
6weshowthattheTBLSandGLSmodelscapturethesamesetofgraphsearches.
Insection6.
7weproposeauniedmethodfortesting,andcertifying,ifagivenorderingoftheverticesmaybeproducedbyagivengraphsearch;wealsopresentacommonimplementationframework.
Finally,wepresentanewgraphparameterbasedonourframework.
ManyoftheresultsofthischapterisacommonworkwithD.
G.
Corneil,M.
Habib,A.
Mamcarz,F.
deMontgolerandsubmitted[CDH+].
6.
2TBLS,aTie-BreakingLabelSearchAgraphsearchisaniterativeprocessthatchoosesateachstepavertexofthegraphandnumbersit(from1ton).
Eachvertexischosen(alsosaidvisited)exactlyonce(evenifthegraphisdisconnected).
LetusnowdeneaGeneralTie-BreakingLabelSearch(TBLS).
Ituseslabelstodecidethenextvertextobevisited;label(v)isasubsetof{1,.
.
.
,n}.
ATBLSisdenedon:1.
AgraphG=(V(G),E(G))onwhichthesearchisperformed;2.
Astrictpartialordersearchorderingorvisitingordering.
Letussayavertexvisunnumbereduntilσ(i)←visperformed,andtheniisitsvisitingdate.
label(v)isalways,thankstothefollowingalgorithm,thesetofvisitingdatesoftheneighborsofvvisitedbeforev.
Morespecicallylabeli(v)foravertexvdenotesthelabelofvatstepi.
Thisformalismidentiesasearchwiththeorderingsitmayproduce,asin[CK08],whileextendingtheformalismofGeneralLabelSearch(GLS)of[KSB11]bytheintroductionofatie-breakorderingτ,makingtheresultofasearchalgorithmpurelydeterministic(noarbitrarydecisionistaken).
946.
2TBLS,aTie-BreakingLabelSearchAlgorithm12:TBLS(G,searcheswewillconsiderappearin[CK08]or[Gol04]orchapter1.
Withthisformalism,inordertospecifyaparticularsearchwejustneedtospecifysearch.
Thechoiceofpermutationτisusefulinsomesituationsdescribedbelow;otherwise,weconsidertheorderingsoutputbyanarbitrarychoiceofτthankstothefollowingdenition:Denition6.
2.
1.
Letsearches,wepointoutsomefeaturesoftheTBLSformalism.
Remarksonthisformalism:1.
NoticethatduringaTBLSsearchverticesarealwayslabeledfrom1upton.
TheoriginaldescriptionofLBFSgeneratedlabelsfromndownto1.
Sincealabelisalwaysanunorderedsetratherthanastring,asoftenseenwithLBFSandLDFS,weavoidhavingtoprependorappendelementstoexistinglabels.
ItshouldalsobenoticedthattheTBLSmodeldoesnotrequirethegraphtobeconnected,andthereforeinthefollowingwewillextendclassicalgraphsearchestodisconnectedgraphs.
Sincewejustneed956.
TBLS:ANEWMODELFORGRAPHSEARCHtospecifysearchnoimplementationdetailshavetobediscussedinthespecicationofthesearch.
Finally,byrequiringatie-breakingpermutationτweimmediatelyhaveamechanismforchoosingaspecicvertexfromEligible.
Manyexistingrecognitionalgorithmssuchastheunitintervalrecognitionalgorithmin[Cor04b]useaseriesofLBFSsweepswheretiesarebrokenbychoosingtherightmosteligiblevertexinthepreviousLBFSsearch;toaccomplishthisintheTBLSformalismτissettobethereverseofthepreviousLBFSordering.
2.
NotethatallelementsofthesetEligiblemusthavealabelsetthatismaximalwithrespecttosetinclusionoversomenitepartiallyorderedset;thereforeEligiblecannotbeempty.
InthecontextofLBFStheEligiblesetisoftencalledaslice.
ThereadershouldbeawarethatwemakenoclaimsonthecomplexityofcomputingthestrictpartialordersearchAisarestrictionofspecicsearchBinthesensethatallpossiblesearchorderingsproducedbysearchAcouldalsohavebeenproducedbysearchB.
Inparticular,wejusthavetoprovethatumin(B).
LetσbeapermutationofV(G).
Thefollowingconditionsareequivalent:1.
σisaBFSordering(aTBLSusingumin(Nσ(y,x))foreveryx,y∈V(G),xsearchesusingTBLS6.
3.
3DFS(DepthFirstSearch)WenowturnourattentiontoDepthFirstSearch.
Theorem6.
3.
4.
WedeneALetσbeapermutationofV(G).
Thefollowingconditionsareequivalent:1.
σisaDFSordering(aTBLSusing2.
foreverytripleofverticesa,b,csuchthata<σb<σc,a∈N(c)N(b)thereexistsd∈N(b)suchthata<σd<σb.
3.
foreverytripleofverticesa,b,csuchthata<σb<σc,andaistherightmostvertexofN(b)∪N(c)inσ,wehavea∈N(b).
Proof.
Theequivalencebetweencondition(1)and(2)hasbeenprovedin[CK08].
Letusshowtheequivalencebetween(1)and(3).
SupposethatσisaDFSor-dering.
UsingLemma6.
3.
1onσ,weknowthat:σisaDFSorderingforeveryx,y∈V(G),x<σy,Nσ(x,x)6.
3.
4LBFS(LexicographicBreadthFirstSearch)LetusnowconsiderLBFS.
Theorem6.
3.
5.
WedeneALetσbeapermutationofV(G).
Thefollowingconditionsareequivalent:1.
σisaLBFSordering(aTBLSusingforeverytriplea,b,c∈V(G)suchthata<σb<σc,a∈N(c)N(b),thereexistsd<σa,d∈N(b)N(c).
996.
TBLS:ANEWMODELFORGRAPHSEARCH3.
foreverytriplea,b,c∈V(G)suchthata<σb<σcandaistheleftmostvertexofN(b)N(c)inσ,thena∈N(b)N(c).
Proof.
Theequivalencebetween(1)and(2)iswellknown,see[RTL76,Gol04,BDN97].
Wenowprovetheequivalencebetween(1)and(3).
SupposethatσisaLBFSordering.
UsingLemma6.
3.
1onσ,weknowthat:σisaLBFSorderingforeveryx,y∈V(G),x<σy,Nσ(x,x)6.
3.
5LDFS(LexicographicDepthFirstSearch)TheLexicographicDepthFirstSearch(LDFS)wasintroducedin[CK08].
Theorem6.
3.
6.
WedeneALetσbeapermutationofV(G).
Thefollowingconditionsareequivalent:1.
σisaLDFSordering(aTBLSusingforeverytriplea,b,c∈V(G)suchthata<σb<σc,a∈N(c)N(b),thereexistsa<σd<σb,d∈N(b)N(c).
3.
foreverytriplea,b,c∈V(G)suchthata<σb<σcandaistherightmostvertexinN(b)N(c)inσ,a∈N(b)N(c).
Proof.
Theequivalencebetween(1)and(2)iswellknown,see[CK08].
Wenowprovetheequivalencebetween(1)and(3).
SupposethatσisaLDFSordering.
UsingLemma6.
3.
1onσ,weknowthat:σisaLDFSorderingforeveryx,y∈V(G),x<σy,Nσ(x,x)3CharacterizingclassicalsearchesusingTBLSNσ(x,x))foreveryx,y∈V(G),x<σy,umax(Nσ(y,x)Nσ(x,x))≤umax(Nσ(x,x)Nσ(y,x))foreverytripleofverticesa,b,csuchthata<σb<σcandaistherightmostvertexofN(b)N(c)inσ,wehavea∈N(b)N(c).
ThesymmetrybetweenBFSandDFS(respectivelyLBFSandLDFS)becomesclearwhenusingtheTBLSorderingformalism.
Thissymmetrywasalsoclearusingthepattern-conditionsasintroducedin[CK08],andinfactleadtothediscoveryofLDFS.
Tonishwithclassicalsearches,wenoticethatMaximalCardinalitySearch(MCS)asintroducedin[TY84],caneasilybedenedusingthepartialorder:ASimilarlyMNS(MaximalNeighborhoodSearch)asintroducedin[Shi84]forchordalgraphrecognition,isasearchsuchthatAe.
,itusesthestrictinclusionorderbetweensubsets.
6.
3.
6LimitationsoftheTBLSmodelTonish,letusremarkthatthereexitsatleastoneknownsearchthatdoesnottintotheTBLSmodel.
Inthefollowing,recallthatlabeli(v)foravertexvdenotesthelabelofvatstepi.
LayeredSearchstartsatavertexs,andensuresthatifdist(s,x)Inotherwordsitrespectsthelayers(verticesatthesamedistancefromthestartvertexs).
WenowshowthatthissearchisnotaTBLSbyconsideringthegraphGingure6.
1.
AssumethatwehavestartedtheLayeredSearchwithx1,x2,x3,x4andsolabel5(x5)={3}andlabel5(x6)={4}.
Inalayeredsearch,bothx5andx6mustbeeligibleatstep5.
Thuswemusthaveneither{3}<{4}nor{4}<{3};theyareincomparablelabels.
ButnowconsidergraphHingure6.
1andassumethatagainwehavestartedthesearchwithv1,v2,v3,v4.
Sowehavelabel5(v5)={3}andlabel5(v6)={4}.
Butinthisgraphwehavetovisitv5beforev6.
Thereforewemusthave{3}<{4}.
Asaconclusion,forLayeredSearchthelabelsarenotsucientandsothissearchcannotbewritteninourformalism.
Thesameseems1016.
TBLS:ANEWMODELFORGRAPHSEARCHtrueforMin-LexBFSasdenedin[Mei05]andRightMostNeighborasusedin[CDH13].
x1x2x3x4x5x6v1v2v3v4v5v6Figure6.
1:GraphGontheleftandHontheright.
6.
4TwonewlexicographicsearchesInthissection,wepresenttwonewsearchesbasedonthesymmetrywithLBFSandLDFS.
Theyhavebeenrststudiedin[Dus10].
InLBFS,weappendnumbersfromnto1andinLDFS,weprependnumbersfrom1ton.
Wenowstudythesearchthatappendsnumbersfrom1ton(LexUP)andthesearchthatprependsnumbersfromnto1(LexDOWN).
6.
4.
1LexUPWestartbypresentingLexUPundertheformofanalgorithm.
Algorithm13:LexUPData:G=(V(G),E(G))anundirectedgraphResult:anorderingσoftheverticesofG1assignlabeltoallvertices;2for(i=1to|V(G)|)do3pickanyunnumberedvertexuwithlexicographicallylargestlabel;4σ(i)←u%{givetouthenumberi}%;5foreach(unnumberedvertexv∈N(u))do6appenditolabel(v);7end8end9Outputσ;1026.
4TwonewlexicographicsearchesFigure6.
2:AgraphGFirst,considerthegraphinFigure6.
2.
ALexUPorderingisforexamplea,b,c,e,d,f.
LetusnowexpressLexUPundertheTBLSformalismbydeningInLexUP,alabelisawordcomposedofnumbersinincreasingorder.
Sofortwolabelsla,lbbuiltbyLexUP,laislexicographicallylessthanlbifandonlyiflaisastrictprexoflbortherstletterinthelabelstheydieronislessinla.
SoATheorem6.
4.
1.
WedeneALetσbeapermutationofV(G).
Thefollowingconditionsareequiv-alent:1.
σisaLexUPordering(aTBLSusingforeverya,b,c∈V(G)suchthata<σb<σcandaistheleftmostvertexofN(b)N(c),ifac∈Ethenthereexistsd∈V(G),a<σd<σb,db∈E(G)andifab∈E(G)thenthereisnovertexdsuchthata<σd<σb,dc∈E(G).
Proof.
SupposethatσisaLexUPordering.
UsingLemma6.
3.
1onσ,weknowthat:σisaLexUPorderingforeveryx,y∈V(G),x<σy,Nσ(x,x)TBLS:ANEWMODELFORGRAPHSEARCHforeveryx,y∈V(G),x<σy,Nσ(y,x)=Nσ(x,x)or((Nσ(y,x)Nσ(x,x))and(umax(Nσ(y,x))Itshouldbenotedthatumin(Nσ(y,x)Nσ(x,x))foreverya,b,c∈V(G)suchthata<σb<σcandaistheleftmostvertexofN(b)N(c),ifac∈Ethenthereexistsd∈V(G),a<σd<σb,db∈E(G)andifab∈E(G)thenthereisnovertexdsuchthata<σd<σb,dc∈E(G).
6.
4.
2LexDOWNWenowconsiderLexDOWNandstartbypresentingLexDOWNundertheformofanalgorithm.
Algorithm14:LexDOWNData:G=(V(G),E(G))anundirectedgraphResult:anorderingσoftheverticesofG1assignlabeltoallvertices;2for(i=1to|V(G)|)do3pickanyunnumberedvertexuwithlexicographicallylargestlabel;4σ(i)←u%{givetouthenumberi}%;5foreach(unnumberedvertexv∈N(u))do6prepend|V(G)|itolabel(v);7end8end9Outputσ;First,considerthegraphinFigure6.
2.
ALexDOWNorderingisforexamplea,b,d,c,f,e.
LetusnowexpressLexDOWNundertheTBLSformalismbydeningInLexDOWN,alabelisawordcomposedofnumbersinincreasingorder.
Sofor1046.
4Twonewlexicographicsearchestwolabelsla,lbbuiltbyLexDOWN,laislexicographicallylessthanlbifandonlyiflaisastrictprexoflbortherstletterinthelabelstheydieronislessinla.
SoATheorem6.
4.
2.
WedeneALetσbeapermutationofV(G).
Thefollowingconditionsareequivalent:1.
σisaLexDOWNordering(aTBLSusingforeverya,b,c∈V(G)suchthata<σb<σcandaistherightmostvertexofN(b)N(c),ifac∈Ethenthereexistsd∈V(G),d<σa,db∈E(G)andifab∈E(G)thenthereisnovertexdsuchthatd<σa,dc∈E(G).
Proof.
SupposethatσisaLexDOWNordering.
UsingLemma6.
3.
1onσ,weknowthat:σisaLexDOWNorderingforeveryx,y∈V(G),x<σy,Nσ(x,x)foreverya,b,c∈V(G)suchthata<σb<σcandaistherightmostvertexofN(b)N(c),ifac∈Ethenthereexistsd∈V(G),d<σa,db∈E(G)andifab∈E(G)thenthereisnovertexdsuchthatd<σa,dc∈E(G).
1056.
TBLS:ANEWMODELFORGRAPHSEARCH6.
5TBLShierarchyofsearchesHereweexplainhowhierarchiesofsearchesmaybebuiltusingtheTBLSfor-malism.
TherearetwonaturalwaysofsayingthatasearchSisasearchS(forinstance,thatLBFSisaBFS):eithertheWestartwiththedenitionofanextensionofaTBLSsearch.
Denition6.
5.
1.
FortwoTBLSsearchesS,S,wesaythatSisanextensionofS(denotedbySS)ifandonlyifeveryS-orderingσalsoisanS-ordering.
1Thestatementandproofofthenextlemmafollowstheworkof[KSB11]wheretherearesimilarresultsfortheGLSformalism.
Lemma6.
5.
2(see[KSB11]).
ForanyTBLSS,anyintegerp≥1andanysetsAandBofP(N+p),ifAe.
,labelp1(σ1(p1))=Aandlabelp1(σ1(p))=B).
Proof.
LetG=(V(G),E(G)),withV(G)={z1,.
.
.
,zp}andE(G)={zizk|1≤kLetσ=(z1,zp).
BythedenitionsofE(G)andσ,foranyintegersi,jsuchthat1≤i≤j≤p,Nσ(σ1(j),σ1(i))=A∩P(N+i)orNσ(σ1(j),σ1(i)=B∩P(N+i)withNσ(σ1(i),σ1(i))ByLemma6.
3.
1,σisanSorderingandwehaveNσ(σ1(p1),σ1(p1))=AandNσ(σ1(p),σ1(p1))=B.
Therelationshipsamongstgraphsearcheshasbeenamainissueinthearti-cles[CK08,KSB11].
Butinbotharticles,provingrelationshipsamongstgraphsearchesrequiredpropertiesonthosegraphsearches.
Thenexttheoremshowshowtoexhibitsuchrelationshipswithoutrequiringanyparticularpropertybe-yondthe1Thisdenitionisconsistentwiththeusualextensionorderingusedinpartialordertheory;inparticularSSmeansthatthesetofcomparabilitiesinSisincludedinthoseofS.
1066.
5TBLShierarchyofsearchesDenition6.
5.
3.
FortwopartialordersTheorem6.
5.
4.
LetS,SbetwoTBLS.
SisanextensionofSifandonlyifProof.
Fortheforwarddirection,assumeforcontradictionthatSisanextensionofSbutThereforethereexistsA,BsuchthatANowusingthepreviouslemmathereexistsagraphGandanS-orderingσsuchthatlabelp1(σ1(p1))=Aandlabelp1(σ1(p))=B.
SinceA3.
1,wededucethatσisnotanS-orderingwhichcontradictsthefactthatSisanextensionofS.
SupposethatσisanS-ordering.
ThereforeusingLemma6.
3.
1weknowthatforeveryx,y∈V(G),x<σy,Nσ(x,x)SinceNowusingtheprevioustheorem,wededucethatσisanS-ordering.
Wenowusethistheoremtoeasilyrediscovertherelationshipsamongstvariousgraphsearchesasnotedin[CK08]and[KSB11].
LBFSLDFSMCSMNSBFSDFSGenericSearchLexUPLexDOWNFigure6.
3:Summaryoftheheredityrelationshipsprovedintheorem6.
5.
5.
AnarcfromSearchStosearchSmeansthatSextendsS.
Theorem6.
5.
5.
ThepartialorderoftherelationextensionbetweenclassicalsearchesisdescribedinFigure1.
Proof.
Toshowthatasearchextendsanotheronewewillusetheorem6.
5.
4.
LetusshowthatLetABydenitionwehaveA=andB=.
Asaconsequencewehave1076.
TBLS:ANEWMODELFORGRAPHSEARCHumin(B)LetusshowthatLetABydenitionwehaveA=andB=.
Asaconsequencewehave(umax(A)WenowshowthatLetABydenition,wehaveumin(B)Asaconsequence,umin(BA)ToseethatThereforeumax(A)SimilarlyLetAAsaconsequence,umin(BA)SoA6.
6TherelationshipbetweenGLSandTBLSWearenowinterestedindeterminingtherelationshipbetweenTBLSandGLS.
FirstletusrecallGLSfrom[KSB11].
Itdependsonalabelingstructurewhichconsistsoffourelements:asetoflabelsL;astrictorderTheGLSalgorithmthentakesasinputagraphG=(V(G),E(G))(overwhichthesearchisperformed)aswellasalabelingstructure.
ThecomputationalpoweroftheUPLABfunctionisunbounded,eventhoughitmustbedeterministic,andthelabelsetLmaybeanyset.
Incontrast,TBLS1086.
6TherelationshipbetweenGLSandTBLSusesnoinitiallabel,axedlabelsetP(N+),andaxedsimpleupdatingfunction.
Despitetheserestrictions,itis,howeverequivalenttoGLSinthesenseoftheorem6.
6.
3.
Algorithm15:GLS(G,{L,e.
,thosewithl(v)maximalwithrespecttoFirstweestablishsomenotation.
AteachiterationiofTBLS(G,e.
,thelabelthatwillbeusedtochoosetheithvertex.
Similarly,letlGLS,i(v)bethelabelassignedtovbyGLS(G,{L,e.
,thelabelthatwillbeusedtochoosetheithvertex.
GivenagraphG=(V(G),E(G)),andanorderingσofV(G),letusdeneIσk(v)=N(v)∩{σ(1)σ(k)}tobetheneighboursofvvisitedatstepk.
Letusdenepjktobethej-thelementofIσk(v)sortedinincreasingvisitingorder.
Proposition6.
6.
1([KSB11]).
LetSbealabelingstructure,G=(V(G),E(G))agraph,andv∈V(G).
AtiterationiofGLS(G,S),lGLS,i(v)=UPLAB(UPLAB(.
.
.
UPLAB(lo,p1i1)p|Iσk(v)|1i1),p|Iσk(v)|i1)Proposition6.
6.
2.
LetG=(V(G),E(G))beagraph,v∈V(G),andσtheorderproducedbyTBLS(G,<,τ).
AtiterationiofTBLS(G,<,τ),lTBLS,i(v)=Iσi1(v).
Proof.
Theproofgoesbyinduction.
Attherststepofthealgorithm,everyvertexhasasitslabel,andhasnopreviouslyvisitedneighbor.
1096.
TBLS:ANEWMODELFORGRAPHSEARCHAssumethatatiterationi,everyunnumberedvertexxhaslabellTBLS,i(x)=Iσi1(x).
Afterthisiteration,foreveryneighborvofσ(i),lTBLS,i(v)=lTBLS,i1(v)∩{i},whichisindeedIσi(v),andforeverynon-neighborvofσ(i),lTBLS,i(v)=lTBLS,i1(v),whichisagainIσi(v).
Theorem6.
6.
3.
AsetToforderingsoftheverticesofagraphGisequalto{TBLS(G,Proof.
First,consideranorder{TBLS(G,Conversely,considerS=(L,WeshowthatthereexistsanorderBypropositions6.
6.
1and6.
6.
2wecandeneaninjectionφfromP(N+)(thelabelsusedbyTBLS)intolabelseectivelyusedbyGLS(i.
e.
thosewhocanbewornbyavertexduringsomeexecutionofthealgorithm).
φisrecursivelydenedasφ()=l0,andifmax(A)=i,thenφ(A)=UPLAB(φ(A)\{i},i).
NoticethesameGLS-labellmaybereachedindierentways.
φ1(l)P(N+)isthesetofTBLS-labelsthatcorrespondtothatlabel.
Itisemptyforalllabelsnoteectivelyused.
Then,wedeneWearenowreadytoprovethetheorem.
Theproofgoesbyinduction.
Beforetherstiteration,foreveryvertexv,l0GLS(v)=l0andl0TBLS(v)=.
GLScanpickanyofthesevertices,inparticulartheonethatwouldbepickedbyTBLS(G,Now,assumethatwhenstepibegins,bothalgorithmshaveproducedtheorderσ(1).
.
.
σ(i1),andtheithvertexisabouttobechosen.
Byproposi-tions6.
6.
1and6.
6.
2,foreveryunnumberedvertexx,lTBLS,i(x)=Iσi1(x),andlGLS,i(x)=lGLS,i(v)=UPLAB(.
.
.
UPLAB(lo,p1i1)p|Iσk(v)|i1).
Bythedeni-tionofφ,wehavethatlGLS,i(x)=φ(lTBLS,i(x)),andlTBLS,i(x)∈φ1(lGLS,i(x)).
1106.
7Test,certicationandimplementationThen,bythedenitionofThus,thesetofeligibleverticesatstepiisthesameforbothalgorithms.
GLScanpickanyofthesevertices,inparticulartheonethatwouldbepickedbyTBLS(G,AlthoughTBLSandGLScoverthesamesetofvertexorderings,wethinkthatourTBLSformalismprovidesasimplerframeworktoanalysemultisweepalgorithms,ascanbeseeninthenextsection.
6.
7Test,certicationandimplementationWenowturnourattentiontothequestionoftestingandcertifyingagivensearch.
Thetestingproblemis:givenanorderingσandasearche.
,doesthereexistτsuchthatσ=TBLS(G,<,τ))Whenthisquestionisasked,nojusticationisneededandsowecanusethealgorithmitself.
Thecerticationproblemis:givenanorderingσandasearchToanswerthisquestionwecannotusetheoriginalalgorithm.
Thedierencebetweenthetwoproblemsisimportantfromapracticalper-spective.
ThecerticationproblemisconcernedwiththeproblemoftrustinganimplementationofasearchS,contrarytothetestingproblemwhichassumesthatthereexistsagoodimplementationofasearchSthatcanbeused,andsimplyanswersyesorno,i.
e.
,adecisionproblem.
6.
7.
1TestingaTBLSThemainresultofthissectionistopresentanalgorithmthatwilltestaTBLS.
RecallfromDenition6.
2.
1thatσisaTBLSorderingforGand1116.
TBLS:ANEWMODELFORGRAPHSEARCHTheorem6.
7.
1.
Let:Gbeagraph;Thenthereexistsτsuchthatσ=TBLS(G,<,τ)ifandonlyifσ=TBLS(G,<,σ).
Proof.
Onedirectionisobvious.
Fortheotherdirection,assumethatσ=TBLS(G,<,τ)forsomeτ,andconsiderσ=TBLS(G,<,σ).
Assume,bycon-tradiction,thatσ=σ,andconsideri,theindexoftherstdierencebetweenσandσ.
LetEligibleσibethesetofeligibleverticesatstepiofthealgo-rithmthatgeneratedσ,andletEligibleσibethesetofeligibleverticesatstepiofthealgorithmthatgeneratedσ.
Sinceσandσareequaluntilindexi,Eligibleσi=Eligibleσi.
BythedenitionofTBLS,σ(i)istherstvertexofEligibleσiaccordingtoτ.
Finally,sincetherstvertexofthisset,accordingtoσ,isσ(i),thetie-breakrulechoseitandsoσ(i)=σ(i),acontradiction.
ThemainissuewiththisalgorithmisthatinordertoverifywhetheranorderingisindeedanS-orderingornot,onehastotrusttheimplementationofS.
Acommonmethodtoavoidthisproblemistheuseofcerticates,whicharewitnessesthataresimpletotest.
Forasurveyoncertifyingalgorithms,wereferthereaderto[MMNS11].
6.
7.
2CertifyingthatanorderingisproducedbyagivensearchUsingTheorem6.
7.
1wecanbuildanalgorithmthattestswhetherornotσ=TBLS(G,<,σ)forsomexed<.
Letτ=TBLS(G,<,σ).
Ifτ=σthentheanswerisyes;otherwiseitisno.
Wecancertifythenoanswerusingtherstdierencebetweenτandσ.
Letibetherstindexsuchthatσ(i)=τ(i).
IfTBLSchoosesσ(i)andnotτ(i)atstepi,thenatthistimel(σ(i))Sowemustbeabletobuildacontradictiontothepattern-conditionofthissearch.
Thenexttheoremimprovesresultsproposedin[KSB11].
Theorem6.
7.
2.
BFS,DFS,LBFSandLDFShaveacerticatewithO(n2)spacecomplexitythatcanbebuiltandtestedinO(n2)timeforBFSandDFSandO(nm)timeforLBFSandLDFS.
1126.
7Test,certicationandimplementationProof.
TobuildthecerticatewewillusethethirdconditionofthefourrelevanttheoremsinSection6.
3,inparticularTheorems6.
3.
3(BFS),6.
3.
4(DFS),6.
3.
5(LBFS)and6.
3.
6(LDFS).
Alloftheseconditionsarepattern-conditions.
Thecerticateisstoredinatablewhoseentriesarekeyedbythepair(b,c)whereb<σcandtheinformationwilleitherbethevertexa,wherea<σbthatsatisesthecorrespondingconditionoranerrormessageindicatingthattheconditionhasbeenviolated.
Forthenon-lexicographicsearchesthepattern-conditionexaminesa,theleftmost(BFS)ortherightmost(DFS)vertexofN(b)∪N(c)andrequiresthata∈N(b).
Usingstraightforwardtechniques(includingsortingalladjacencylistsaccordingtoσ)itcanbeshownthatthiscanbeaccomplishedinconstanttime,foranybandc.
Forthelexicographicsearches,thepattern-conditionex-aminesa,theleftmost(LBFS)ortherightmost(LDFS)vertexofN(b)N(c)andrequiresthata∈N(b)N(c).
Again,itiseasytoshowthatthiscanbeaccomplishedintimeO(|N(b)|+|N(c)|,foranybandc.
Inallcases,ifasatis-esthemembershipconditionthenitisstoredintheb,c'thentryofthetable;otherwise"error"isstored.
Regardingcomplexityconsiderations,thetablegivesustheO(n2)spacecom-plexity.
Forthenon-lexicographicsearchesO(n2)timeisrequiredtobuildandsearchthetable.
Forthelexicographicsearches,thetimingrequirementisboundedbyb∈V(G)c∈V(G)(|N(b)|+|N(c)|)tobuildthetableandO(n2)timetosearchit,givinganO(nm)timingcomplexity.
6.
7.
3ImplementationItisnothardtoverifythatclassicalsearchessuchasBFS,DFS,LBFS,LDFS,canbeimplementedasaTBLSsearch,i.
e.
,solvingthetie-breakwithagiventotalorderingτofthevertices,withinthesamecomplexityastheircurrentbestimplementations.
WenowproveanupperboundvalidforallTBLSsearches.
Theorem6.
7.
3.
TBLS(G,<,τ)canbeimplementedtoruninO(mT(n)logn)timewheretheProof.
Weusetheframeworkofpartitionrenement[HMPV00].
Firstwesorttheadjacencylistswithrespecttoτ,andconsiderthefollowingalgorithm.
TheinputtothealgorithmisagraphG=(V(G),E(G)),anorder1136.
TBLS:ANEWMODELFORGRAPHSEARCHAlgorithm16:ComputingaTBLSorderingLetPbethepartition{V(G)},wheretheonlypartV(G)isorderedwithrespecttoτ;fori←1tondoLetEligiblebethepartofPwiththelargestlabelwithrespecttoEachpartofPisanorderedlistofvertices.
Thefollowingtwoinvariantsholdthroughouttheexecutionofthealgorithm:1.
Theverticesofeachparthavethesameunique(withrespecttoparts)label;2.
Insideapart,theverticesaresortedwithrespecttoτ.
TheactionofRene(P,A)istoreplaceeachpartP∈Pwithtwonewparts:P∩AandPA(ignoringemptynewparts).
Itispossibletomaintainthetwoinvariantsusingthedatastructurefrom[HMPV00],providedtheadjacencylistsofGaresortedwithrespecttoτ.
Aftereachrenement,eachpartofPthereforecontainsverticesthataretwinswithrespecttothevisitedvertices(Invariant1).
Thankstothesecondinvariant,thechosenvertexisalwaystherstvertex(withrespecttoτ)ofpartEligible;i.
e.
,σ(i)isindeedx.
Forthetimecomplexity,Rene(P,N(x))takesO(|N(x)|)time[HMPV00],soallrenementstakeO(n+m)time.
Theonlynon-linearstepisidentifyingpartEligibleamongallpartsofthepartition.
Eachparthasalabel(theonesharedwithallitsvertices)usedasakeyinaMax-Heap.
Rene(P,N(x))createsatmost|N(x)|newpartssothereareatmostminsertionsintheheap.
Thelabelofapartdoesnotchangeovertime(butemptypartsmustberemoved).
Therearenofewerremovaloperationsthaninsertionoperations,eachconsistingofatmostlognlabelcomparisons(sincethereareatmostnpartsatanytime).
SowegettheO(mT(n)logn)timebound.
1146.
8Application:theTBLSdimension,anewgraphparameter6.
8Application:theTBLSdimension,anewgraphparameterEventhoughthereexistssearchesthatarenotTBLSs,ourmodelispowerfulenoughtoexpressmanygraphalgorithms.
Inthefollowing,wewillfocusontheTBLSthatarepolynomiallycomputable(i.
e.
theonesinwhichtwolabelscanbecomparedinpolynomialtime),andletusnowfocusourattentiononmultisweepTBLSalgorithms.
AmultisweepTBLSalgorithmisanalgorithmthatcomputesaseriesoforderingandoutputsthelastorderingcomputed.
Therstorderingσ0isanyorderingoftheverticesandthentheorderingσiisobtainbyperformingTBLS(G,ForagivenpropertyPandaclassofgraphC,letusdenetheTBLSdimensionofP,C(denotedbytblsdim(P,C)astheminimalnumberofTBLSthatamultisweepTBLSalgorithmneededtoperforminordertocomputeforeverygraphG∈CanorderingthatsatisfythepropertyP.
Thisnewparametermeasurestheeciencyofgraphsearchtocomputesomegraphproperty,butitalsorevealsstructuralaspectsofgraphclassesasitwillbediscussednext.
Manystructuredclassesofgraphs,suchascographs,interval,chordal.
.
.
canbecharacterizedbytheexistenceofanorderingoftheverticessatisfyingagivenproperty,resp.
intervalordering,simplicialordering.
.
.
ItiswellknownthatGisachordalgraphifandonlyifthereexistsanorderingσsuchthatforeveryx<σy<σz,ifxz,yz∈E(G)thenxy∈E(G).
Thiskindoforderingwillbecalledasimplicialeliminationordering.
Ithasbeenprovedin[TY84],thatperformingaLBFSyieldsasimplicialeliminationorderingifandonlyifthegraphischordal.
ThereforetheTBLSdimensionofσisasimplicialeliminationorderingfortheclassofchordalgraphsis1.
Thecographrecognitionalgorithmpresented[BCHP08]usesonlyoneLBFS+andthenoneLBFS+onthecomplement.
Inthearticle,theauthorsexplainhowtoperformaLBFSonthecomplementwithoutcomputingthecomplement;thisisdonebytakingtheinverseofThereforetblsdim(Cograph)≤2.
Itiswell-knownfrom[Rob71]thatagraphGisaunitintervalgraphifandonlyifthereexistsanorderingσsuchthatforeveryx<σy<σz,ifxz∈E(G)1156.
TBLS:ANEWMODELFORGRAPHSEARCHthenxy,yz∈E(G).
Thiskindoforderingwillbecalledanunitintervalorder-ing.
In[Cor04b],aTBLSmultisweepalgorithmhasbeenfoundtondanunitordering.
Thisalgorithmuses3consecutiveLBFS+.
Thereforetblsdim(ProperInterval)≤3.
In[KS93],ithasbeennoticedthatGisacocomparabilitygraphifandonlyifthereexistsanorderingσsuchthatforeveryx<σy<σz,ifxz∈E(G)thenxy∈E(G)oryz∈E(G).
Suchanorderingiscalledacocompordering.
Inchapter5,ithasbeenprovedthatperformingnLBFS+alwaysyieldsacocomporderingifthegraphisacocomparabilitygraph.
Thereforetblsdim(Cocomp)≤n.
Asaconsequencetblsdim(Permutation)≤2nandtblsdim(Interval)≤n.
Itshouldbenoticedthatwedonotknowanygraphsearchbasedrecognitionalgorithmforpermutationgraphs,thereforethisboundcouldbefarfrombeingoptimal.
ThefollowingpicturesumsupsomeknownresultsaboutTBLSbasedrecognitionalgorithmsforwell-knowngraphclasses:ProperInterval(≤3)Cograph(≤2)Interval(≤n)Permutation(≤2n)Chordal(1)Cocomparability(≤n)Comparability(≤n)Perfect()6.
9ConcludingremarksWehavefocusedourstudyonanewformalismthatcapturesmanyusualgraphsearchesaswellasthecommonlyusedmulti-sweepapplicationofthesesearches.
TheTBLSformalismallowsustodeneagenericTBLS-orderingsrecognitional-gorithm,andgivesusanewpointofviewofthehierarchyamongstgraphsearches.
Thenewpattern-conditionsforLBFSandLDFSgiveusabetterwayofcerti-fyingwhetheragivenorderingisaLBFSorLDFSthanthepattern-conditions1166.
9Concludingremarkspresentedin[CK08].
Furthermore,wedonothavetotrusttheimplementationofthesearch(whichcanbecomplicated)buthavepresentedasimpleprogramthatjustvisitstheneighborhoodoftheverticesofthegraphandstoresasmallamountofinformation(seeTheorem6.
7.
2).
Thesizeofthisextrainformation,however,canbebiggerthanthesizeoftheinput,anditmaytakelongertocomputethantheactualtimeneededtoperformthesearchitself.
WhilebeingasgeneralasGLS,wefeelthatTBLSisclosertothepattern-conditionspresentedin[CK08],sincemanyoftheStill,therearemanyvariantsofthesearcheswestudiedthatdonotfallundertheTBLS,suchaslayeredsearch.
Wewonderifamoregeneralsearchmodelcanbefound,thatwouldnotonlyincludesomeoftheseothercommonsearchesbutwouldalsoretainthesimplicityofTBLS.
Thelandscapeofgraphsearchisquitecomplex.
Graphsearchescanbeclus-teredusingthedatastructuresinvolvedintheirbestimplementations(queue,stack,partitionrenementInthischapterwehavetriedamoreformalwaytoclassifygraphsearches.
Thisattemptyieldsanalgebraicframeworkthatcouldbeofsomeinterest.
Clearlybeinganextension(seesection6.
5)isatransitiverelation.
InfactstructurestheTBLSgraphsearchesas∧-semilattice.
The0searchinthissemi-lattice,denotedbythenullsearchorSnull,correspondstotheemptyorderingrelation(nocomparablepairs).
AteverystepofSnulltheEligiblesetcontainsallunvisitedvertices.
Thereforeforeveryτ,TBLS(G,TheinmumbetweentwosearchesS,Scanbedenedasfollows:ForeverypairoflabelsetsA,B,wedene:AClearlyeveryextensionofSandSisanextensionofS∧S.
SimilarlySandSareextensionsofS∧S.
1176.
TBLS:ANEWMODELFORGRAPHSEARCH118ANotationA.
1SetsandbinaryrelationsAsetSisacollectionofelementx∈S.
ThecardinalityofasetSisdenotedby|S|.
Thesymbolsarerespectivelydenotedthesubset,strictsubset,intersection,union,dierenceandsymmetricdierenceoperators.
ThecartesianproductofasetSisnotedS*S.
WedenotebyNthesetofintegersgreaterorequalthan0.
N+denotesthesetofintegersstrictlygreaterthan0andbyN+pthesetofintegersstrictlygreaterthan0andlessthanp.
P({1,.
.
.
,n})denotesthepower-setof{1,.
.
.
,n}andSnthesetofallpermutationsof{1,.
.
.
,n}.
DenitionA.
1.
1.
AbinaryrelationRonagroundsetXisanorderedpair(X,E)whereEX*Xand(a,b)∈EiaRb.
A.
2GraphsAgraphG=(V(G),E(G))isabinaryrelation.
Ingraphtheory,wemakethedierencebetweendirectedandundirected.
Agraphisundirectedi(a,b)∈E(G)impies(b,a)∈E(G).
Agraphisdirectedifisnotundirected.
Aloopinagraphisanedge(u,u)forsomevertexu.
Agraphissimpleifithasnoloopandnomultipleedges.
Inthisthesis,allthegraphsarewithoutloopsandmostofthemareundi-rected.
119A.
NOTATIONForconvenience,insteadofdenotinganedgebyaset(x1,x2),wedenoteitbythewordsx1x2andx2x1.
ThereforeforagraphG,E(G)isalsoconsideredasasetoftwoletterwordsoverthealphabetV(G).
ThecomplementofasimplegraphG=(V(G),E(G))isdenedbyG=(V(G),E(G))whereE(G)={(u,v)∈V(G)*V(G)|u=vand(u,v)/∈E(G)}.
ForavertexvinagraphG=(V(G),E(G)),theneighbourhoodofvisdenebyN(v)={x∈V(G)|xv∈E(G)}.
ThevariablenisusedtodenotethenumberofverticesofG,i.
e.
thecardinalityofV(G),andmisusedtodenotethenumberofedgesofG,i.
e.
thecardinalityofE(G).
AnexampleofagraphisgiveningureA.
1.
FigureA.
1:AsimpleundirectedgraphGwhereV(G)={x1,x1,x2,x3,x4,x5,x6}andE(G)={x1x2,x2x3,x3x4,x4x5,x1x5,x1x6,x2x6,x3x6,x4x6,x5x6}DenitionA.
2.
1.
ForagraphG=(V(G),E(G))wesaythatH=(V(H),E(H))isasubgraphofGifandonlyifforeveryx∈V(H),x∈V(G)andforeveryuv∈E(H),uv∈E(G).
DenitionA.
2.
2.
ForagraphG=(V(G),E(G))wesaythatH=(V(H),E(H))isaninducedsubgraphofGifandonlyifHisasubgraphofGandforeveryu,v∈V(H),uv∈E(H)iuv∈E(G).
Apathisagraphwhoseverticescanbearrangedinalinearsequenceinsuchawaythattwoconsecutivesverticesinthesequenceareadjacent.
Aninducedpathisagraphwhoseverticescanbearrangedinalinearsequenceinsuchawaythattwoverticesareadjacentifandonlyiftheyareconsecutiveinthesequence.
Acycleisagraphwhoseverticescanbearrangedinacyclicsequenceinsuchawaythattwoconsecutivesverticesinthesequenceareadjacent.
Aninducedcycleisagraphwhoseverticescanbearrangedinacyclicsequenceinsuchaway120A.
3Ordersthattwoverticesareadjacentifandonlyiftheyareconsecutiveinthesequence.
Thelengthofapathisthenumberofvertices-1.
Acliqueisanundirectedgraphwhereeverypossibleedgeispresent.
Exempleofapath,aninducedpath,acycle,aninducedcycleandancliquecanbefoundinFigureA.
2.
FigureA.
2:Ontherstline:Apathv1,v2,v3,v4,v5andaninducedpathv1,v2,v3,v4,v5.
Onthesecondline:acyclev1,v2,v3,v4,v5andaninducedcyclev1,v2,v3,v4,v5.
AnorderingσofGisabijectionσ:V(G){1,2,.
.
.
,n}.
Thereforeforx∈V(G),σ(x)denotesthepositionofxinσandfora∈{1,2,.
.
.
,n},σ1(a)denotesthevertexatpositionainσ.
Fortwoverticesu,v,wewritethatu<σviσ(u)<σ(v).
ForagraphG=(V(G),E(G)),asubsetSofV(G)iscalledanindependantsetifandonlyifforeveryu,v∈S,uv/∈E(G).
ThemaximumsizeofanindependantsetofGisdenotedbyα(G).
SimilarlyasubsetSofV(G)iscalledacliqueifandonlyifforeveryu,v∈S,u=v,uv∈E(G).
ThemaximumsizeofacliqueofGisdenotedbyω(G).
Ak-propercoloringofagraphG=(V(G),E(G))isapartitionofV(G)intoindependantsetsS1,Sk;acoloringisobtainbyassigningadierentcolortoeachindependantset.
AgraphGisk-colorableifthereexistsak-propercoloringofG.
ThechromaticnumberofagraphG,denotedbyχ(G),isthesmallestvalueksuchthatGisk-colorable.
A.
3OrdersDenitionA.
3.
1.
AbinaryrelationR=(X,E)issaidtobe:reexiveiforeveryu∈X,uRu.
121A.
NOTATIONirreexiveiforeveryu∈X,uRu.
antisymmetriciforeveryu,v∈X,(uRvandvRu)impliesu=v.
transitiveiforeveryu,v,w∈X,(uRvandvRw)impliesuRw.
totaliforeveryu,v∈X,uRvorvRu.
DenitionA.
3.
2.
ApartialorderPisanorderedpair(X,≤P)where≤Pisareexive,antisymmetricandtransitivebinaryrelationoverthegroundsetX.
Aparticularcaseofpartialorderistotalorder.
DenitionA.
3.
3.
AtotalorderTisapartialorder(X,≤T)wherethebinaryrelation≤Tisalsototal.
DenitionA.
3.
4.
AstrictorderSisanorderedpair(X,Inanorder(strictorpartial)P,twoelementsu,v∈XaresaidcomparableiuRvorvRuandincomparableitheyarenotcomparable.
Fortwoincomparableelementsu,v,wedenoteitbyuRv.
FromapartialorderP=(X,≤P)wecanbuildtworelationsthatareoftenused:thestrictrelationthatwearegoingtodenoteby(X,DenitionA.
3.
5.
ForapartialorderP=(X,≤P),thestrictorder(X,DenitionA.
3.
6.
ForapartialorderP=(X,≤),thecoveringrelationdenotedbyPoverXisdenedbyforeveryx,y∈X,xPyixTherelationofcoveringcapturesthestructureoftheposetsincefromthecoveringrelationwecanrebuildtheoriginalposet.
Indeed,fromacoveringrelationQoverXtherelation≤Qisdenedbyforx,y∈X,x≤Qyix=yorthereexistsaseriex0=x,x1,.
.
.
,xj=ysuchthatfor0≤i122A.
3OrdersDenitionA.
3.
7.
Thedirectedcoveringgraph(alsoknownunderthenameHassediagram)ofapartialorderP=(X,≤)isarepresentationofapartialorderbyitscoveringrelationwheretheelementsx∈Xarepointsoftheplanep(x)insuchawaythatthetwofollowingrulesarerespected:Ifxp(x)andp(y)arejoinedbyastraightlineixPy.
Wealsoneedthefollowingdenitions.
DenitionA.
3.
8.
LetP=(X,≤)beanorderedpairwith≤anantisymmetricandtransitivebinaryrelation.
foru∈X,wesaythatuisasourceofPifandonlyifforeveryv∈X,v=u,v≤u,foru∈X,wesaythatuisasinkofPifandonlyifforeveryv∈X,v=u,u≤v,fortwoelementsu,v∈Xwesaythatw∈Xisaminimalelementforu,vifandonlyifw≤uandw≤v,fortwoelementsu,v∈Xwesaythatw∈Xisamaximalelementforu,vifandonlyifu≤wandv≤w.
Wesaythatabinaryrelation(X,Q)extendsabinaryrelation(X,P)ifforeveryx,y∈X,xPyimpliesxQy.
ApartialorderP=(X,≤P)extendsapartialorderQ=(X,≤Q)ithebinaryrelation≤Pextendsthebinaryrelation≤Q.
InthecasethatPisapartialorderandQisatotalorder,wesaythatQisalinearextensionofP.
InapartialorderP=(X,≤P),achainisasetSXsuchthateverypairofelementsiscomparable,i.
e.
foreveryu,v∈S,u≤Pvorv≤Pu.
InapartialorderP=(X,≤P),anantichainisasetSXsuchthateverypairofelementisincomparable,i.
e.
foreveryu,v∈S,u=v,vPu.
ThegraphinducedbyapartialorderP=(X,≤)isthegraphG=(X,E)whereforx,y∈X,xy∈EixAgraphisacomparabilityifandonlyifit'stheinducedgraphofsomepartialorder.
Acocomparabilitygraphisthecomplementofacomparabilitygraph.
123A.
NOTATIONDenitionA.
3.
9.
ApartialorderP=(X,≤P)isalatticeifandonlyifforeverypairofelementsx,y∈Xthereexistsanuniquegreatestminimalelementforx,yandanuniquelowestmaximalelementforx,y.
ForalatticeL=(V,≤L)andtwoelementsx,y∈V,thesinglegreatestminimalelementofx,yiscalledtheinmumorthemeetanddenotedbyx∧Ly;Thesinglelowestmaximalelementofx,yiscalledthesupremumorthejoinanddenotedbyx∨Ly.
AlatticeL=(V,≤L)isalsodenotedbyL=(V,∧L,∨L).
Inthisthesis,weofentalkaboutorderingσorτoftheverticesofagraphG.
FigureA.
3:Ontheleftthedirectedcoveringgraphofalatticeandontherightthedirectedcoveringgraphofaposetwhichisnotalattice.
124References[B.
88]BehrendtB.
Maximalantichainsinpartiallyorderedsets.
ArsCom-binatoria,25C:149–157,1988.
23,24,25[BCHP08]AnnaBretscher,DerekG.
Corneil,MichelHabib,andChristophePaul.
Asimplelineartimelexbfscographrecognitionalgorithm.
SIAMJ.
DiscreteMath.
,22(4):1277–1296,2008.
9,115[BDN97]AndreasBrandst¨adt,FeodorF.
Dragan,andFalkNicolai.
LexBFS-orderingsandpowersofchordalgraphs.
DiscreteMathematics,171(1-3):27–42,1997.
10,100[BPS10]AnneBerry,RomainPogorelcnik,andGenevi`eveSimonet.
AnIn-troductiontoCliqueMinimalSeparatorDecomposition.
Algorithms,3(2):197–215,2010.
55,61[CDH+]DerekG.
Corneil,JeremieDusart,MichelHabib,AntoineMamcarz,andFabiendeMongoler.
Anewmodelforgraphsearch.
submittedatDiscreteAppliedMathematics,specialissueGROWconference.
3,94[CDH13]DerekG.
Corneil,BarnabyDalton,andMichelHabib.
LDFS-basedcertifyingalgorithmfortheminimumpathcoverproblemoncocom-parabilitygraphs.
SIAMJ.
Comput.
,42(3):792–807,2013.
2,11,35,93,102125REFERENCES[CDHK]DerekG.
Corneil,JeremieDusart,MichelHabib,andE.
Kohler.
Onthepowerofgraphsearchingforcocomparabilitygraphs.
inprepara-tion.
2,3,35,62[CK]DerekG.
CorneilandEkkehardK¨ohler.
Unpublishedmanuscript.
77,91[CK08]DerekG.
CorneilandRichardKrueger.
Auniedviewofgraphsearching.
SIAMJ.
DiscreteMath.
,22(4):1259–1276,2008.
1,3,8,9,11,13,93,94,95,96,97,98,99,100,101,106,107,117[CLRS01]ThomasH.
Cormen,CharlesE.
Leiserson,RonaldL.
Rivest,andCliordStein.
IntroductiontoAlgorithms.
TheMITPress,2edition,2001.
1,8,9[Cor04a]DerekG.
Corneil.
Lexicographicbreadthrstsearch-asurvey.
InproceedingsofWG,pages1–19,2004.
1,9[Cor04b]DerekG.
Corneil.
Asimple3-sweepLBFSalgorithmfortherecognitionofunitintervalgraphs.
DiscreteAppliedMathematics,138(3):371–379,2004.
9,18,90,93,96,116[COS09]DerekG.
Corneil,StephanOlariu,andLornaStewart.
TheLBFSstructureandrecognitionofintervalgraphs.
SIAMJ.
DiscreteMath.
,23(4):1905–1953,2009.
1,3,9,18,36,75,77,90,91,93[CT13]ChristopheCrespelleandIoanTodinca.
Ano(n2)o(n2)-timealgo-rithmfortheminimalintervalcompletionproblem.
Theor.
Comput.
Sci.
,494:75–85,2013.
36[DH]JeremieDusartandMichelHabib.
AnewLBFS-basedalgorithmforcocomparabilitygraphrecognition.
submittedatDiscreteAppliedMathematics.
3,9,76,93[DM41]BenDushnikandE.
W.
Miller.
Partiallyorderedsets.
AmericanJournalofMathematics,63(3):pp.
600–610,1941.
33126REFERENCES[DSW88]P.
M.
Dearing,D.
R.
Shier,andD.
D.
Warner.
Maximalchordalsub-graphs.
DiscreteAppliedMathematics,20(3):181–190,1988.
47[Dus10]JeremieDusart.
Parcoursdegraphes.
Master'sthesis,UniversiteParisDiderot,2010.
102[GH64]P.
C.
GilmoreandA.
J.
Homan.
Acharacterizationofcomparabilitygraphsandofintervalgraphs.
Canad.
J.
Math.
,16:539–548,1964.
17,32[Gol04]MartinCharlesGolumbic.
AlgorithmicGraphTheoryandPerfectGraphs(AnnalsofDiscreteMathematics,Vol57).
North-HollandPublishingCo.
,Amsterdam,TheNetherlands,TheNetherlands,2004.
10,14,16,55,95,100[HMPR91]MichelHabib,MichelMorvan,MauricePouzet,andJean-XavierRampon.
Extensionsintervallairesminimales.
InCompteRendu`al'AcademiedesSciences,presenteenseptembre91,parlePr.
G.
Choquet,pages893–898,1991.
36[HMPR92]MichelHabib,MichelMorvan,MauricePouzet,andJean-XavierRampon.
Incidencestructures,codingandlatticeofmaximalan-tichains.
TechnicalReport92-079,LIRMM,1992.
36[HMPV00]MichelHabib,RossM.
McConnell,ChristophePaul,andLaurentViennot.
Lex-BFSandpartitionrenement,withapplicationstotransitiveorientation,intervalgraphrecognitionandconsecutiveonestesting.
Theor.
Comput.
Sci.
,234(1-2):59–84,2000.
11,21,75,77,82,90,113,114[HSTV05]PinarHeggernes,KarolSuchan,IoanTodinca,andYngveVillanger.
Minimalintervalcompletions.
InGerthStltingBrodalandStefanoLeonardi,editors,ESA,volume3669ofLectureNotesinComputerScience,pages403–414.
Springer,2005.
36[Kru05]RichardKrueger.
GraphSearching.
PhDthesis,DepartmentofCom-puterScience,UniversityofToronto,2005.
2127REFERENCES[KS93]DieterKratschandLornaStewart.
Dominationoncocomparabilitygraphs.
SIAMJ.
DiscreteMath.
,6(3):400–417,1993.
14,15,116[KSB11]RichardKrueger,Genevi`eveSimonet,andAnneBerry.
Agenerallabelsearchtoinvestigateclassicalgraphsearchalgorithms.
DiscreteAppliedMathematics,159(2-3):128–142,2011.
2,3,93,94,106,107,108,109,112[LC62]BolandJ.
LekkeikerkerC.
Representationofanitegraphbyasetofintervalsontherealline.
FundamentaMathematicae,51(1):45–64,1962.
17[LW13]PengLiandYaokunWu.
Afour-sweepLBFSrecognitionalgorithmforintervalgraphs.
DiscreteMathematicsandTheoreticalComputerScience,toappear,2013.
9[Ma]T.
Ma.
unpublishedmanuscript.
77,89,91[Mar75]GeorgeMarkowsky.
Thefactorizationandrepresentationoflattices.
TransactionsoftheAmericanMathematicalSociety,203:185–200,1975.
25[Mar92]GeorgeMarkowsky.
Primes,irreductiblesandextremallattices.
Or-der,9:265–290,1992.
25[MC12]GeorgeB.
MertziosandDerekG.
Corneil.
Asimplepolynomialalgo-rithmforthelongestpathproblemoncocomparabilitygraphs.
SIAMJ.
DiscreteMath.
,26(3):940–963,2012.
2,11[Mei05]DanielMeister.
Recognitionandcomputationofminimaltriangu-lationsforat-freeclaw-freeandco-comparabilitygraphs.
DiscreteAppliedMathematics,146(3):193–218,2005.
21,102[MMNS11]RossM.
McConnell,KurtMehlhorn,StephanN¨aherc,andPas-calSchweitzerd.
Certifyingalgorithms.
ComputerScienceReview,5(2):119–161,2011.
112128REFERENCES[MS99]RossM.
McConnellandJeremySpinrad.
Modulardecompositionandtransitiveorientation.
DiscreteMathematics,201(1-3):189–241,1999.
21,51,75[Ola91]StephanOlariu.
Anoptimalgreedyheuristictocolorintervalgraphs.
InformationProcessingLetters,37(1):21–25,1991.
16[Ray87]A.
Raychaudhuri.
Onpowersofintervalandunitintervalgraphs.
Congr.
Numerantium,59:235242,1987.
16[Rob71]FredS.
Roberts.
Onthecompatibilitybetweenagraphandasimpleorder.
JournalofCombinatorialTheory,SeriesB,1971.
115[RR88]G.
RamalingamandC.
PanduRangan.
Auniedapproachtodomi-nationproblemsonintervalgraphs.
Inf.
Process.
Lett.
,27(5):271–274,1988.
16[RT75]DonaldJ.
RoseandRobertEndreTarjan.
Algorithmicaspectsofvertexelimination.
InWilliamC.
Rounds,NancyMartin,JackW.
Carlyle,andMichaelA.
Harrison,editors,STOC,pages245–254.
ACM,1975.
55[RTL76]DonaldJ.
Rose,RobertEndreTarjan,andGeorgeS.
Lueker.
Algo-rithmicaspectsofvertexeliminationongraphs.
SIAMJ.
Comput.
,5(2):266–283,1976.
1,9,10,89,90,100[Sha81]MichaSharir.
Astrongconnectivityalgorithmanditsapplicationstodataowanalysis.
ComputersandMathematicswithApplications,page6772,1981.
93[Shi84]D.
R.
Shier.
Someaspectsofperfecteliminationorderingsinchordalgraphs.
DiscreteAppliedMathematics,7:325331,1984.
1,12,13,101[Spi]J.
Spinrad.
Ecientimplementationoflexicographicdepthrstsearch.
submittedforpublication.
12[Spi03]JerrySpinrad.
EcientGraphRepresentations.
FieldsInstituteMonographs19,AmericanMathematicalSociety,2003.
75129REFERENCES[Tar72]RobertE.
Tarjan.
Depth-rstsearchandlineargraphalgorithms.
SIAMJournalonComputing,1(2):146–160,1972.
7,97[Tar85]RobertEndreTarjan.
Decompositionbycliqueseparators.
DiscreteMathematics,55(2):221–232,1985.
55[TCHP08]MarcTedder,DerekG.
Corneil,MichelHabib,andChristophePaul.
Simplerlinear-timemodulardecompositionviarecursivefactorizingpermutations.
InLucaAceto,IvanDamgard,LeslieAnnGoldberg,MagnusM.
Halldorsson,AnnaIngolfsdottir,andIgorWalukiewicz,editors,ICALP(1),volume5125ofLectureNotesinComputerSci-ence,pages634–645.
Springer,2008.
9[TY84]RobertE.
TarjanandMihalisYannakakis.
Simplelinear-timealgo-rithmstotestchordalityofgraphs,testacyclicityofhypergraphs,andselectivelyreduceacyclichypergraphs.
SIAMJ.
Comput.
,13(3):566–579,1984.
13,101,115[Yan81]M.
Yannakakis.
Computingtheminimumll-inisnp-complete.
SIAMJournalonAlgebraicDiscreteMethods,2(1):77–79,1981.
52,53130ListofAlgorithms1GraphSearchParadigm(GSP)72LBFS103LDFS124Chainclique375LocalMNS416Simplicialverticesinacocomparabilitygraph597Divideandconquer618Listofatoms639RepeatedLBFS+7610Partition8111TransitiveorientationAlgorithm9112TBLS(G,<,τ)9513LexUP10214LexDOWN10415GLS(G,{L,

展开全文

• computationgraph相关文档
• resultsgraphsearch
• reciprocatedgraphsearch
• memorygraphsearch
• nodegraphsearch
• graphgraphsearch
• swappedgraphsearch

王小玉网-美国洛杉矶2核4G 20元/月,香港日本CN2 2核2G/119元/季,美国300G高防/80元/月!

 活动方案：美国洛杉矶 E5 2696V2 2核4G20M带宽100G流量20元/月美国洛杉矶E5 2696V2 2核4G100M带宽1000G流量99元/季香港CN2 E5 2660V2 2核2G30M CN2500G流量119元/季日本CN2E5 2660 2核2G30M CN2 500G流量119元/季美国300G高防 真实防御E5 2696V2 2核2G30M...

月神科技-美国CERA 5折半价倒计时，上新华中100G高防云59起！

官方网站：点击访问月神科技官网优惠码：美国优惠方案：CPU：E5-2696V2，机房：国人热衷的优质 CeraNetworks机房，优惠码：3wuZD43F 【过期时间：5.31，季付年付均可用】活动方案：1、美国机房：洛杉矶CN2-GIA，100%高性能核心：2核CPU内存：2GB硬盘：50GB流量：Unmilited端口：10Mbps架构：KVM折后价：15元/月、150元/年传送：购买链接洛...

盘点618年中大促中这款云服务器/VPS主机相对值得选择

昨天有在"盘点2021年主流云服务器商家618年中大促活动"文章中整理到当前年中大促618活动期间的一些国内国外的云服务商的促销活动，相对来说每年年中和年末的活动力度还是蛮大的，唯独就是活动太过于密集，而且商家比较多，导致我们很多新人不懂如何选择，当然对于我们这些老油条还是会选择的，估计没有比我们更聪明的进行薅爆款新人活动。有网友提到，是否可以整理一篇当前的这些活动商家中的促销产品。哪些商家哪款产...

graphsearch为你推荐

三星iphone支持ipad支持ipadboxiphonephotoshop技术photoshop技术对哪些工作有用？iexplore.exe应用程序错误iexplore.exe应用程序错误tcpip上的netbios网络连接详细信息上的netbios over tcpip是什么意思？ms17-010win10华为 slatl10是什么型号iphonewifi苹果wifi版和4G版是什么意思，有什么区别吗google中国地图谷歌卫星地图中文版下载在哪下？？

vps 高防服务器租用qy 10t等于多少g 美国主机论坛 警告本网站 魔兽世界台湾服务器 e蜗牛 php空间申请 数字域名 idc是什么 世界测速 银盘服务是什么 优酷黄金会员账号共享 789 摩尔庄园注册 杭州电信宽带 双十二促销 tracker服务器 免费赚q币 免费网站加速 更多