Certificate

On-LineAlgorithmsforRankingsof

Graphs

by

MuntasirRaihanRahman(Std.No:0005003)Md.EhtesamulHaque(Std.No:0005017)

MaeenulIslam(Std.No:0005011)

DepartmentofComputerScienceandEngineeringBangladeshUniversityofEngineeringandTechnology(BUET)

Dhaka1000,Bangladesh

November2006

Certificate

ThisistocertifythattheworkpresentedinthisthesispaperistheresultoftheresearchcarriedoutbythecandidatesunderthesupervisionofDr.Md.AbulKashemMiaintheDepartmentofComputerScienceandEngineering,BangladeshUniversityandTechnology,Dhaka,Bangladesh.Itisalsoassertedthatneitherofthisthesisnoranypartthereofhasbeensubmittedorisbeingconcurrentlysubmittedanywhereelsefortheawardofanydegreeordiploma.

Dr.Md.AbulKashemMia(Supervisor)

i

Contents

AcknowledgementsAbstract1Introduction

1.1Backgrounds.................................

1.1.1TheVertex-RankingProblem...................1.1.2GeneralizedVertex-Rankings....................1.1.3TheEdge-RankingProblem....................1.1.4GeneralizedEdge-Rankings....................1.1.5

On-LineRankingsofGraphs....................

1.2ScopeofthisThesis.............................1.3Summary..................................2Preliminaries

2.1BasicTerminology.............................

2.1.1

GraphsandMultigraphs......................

ii

vii1225779101111131314

CONTENTS

2.1.2DegreeofaVertex.........................2.1.3Subgraphs..............................2.1.4PathsandCycles..........................2.1.5ComponentsofaGraph......................2.1.6Trees.................................2.1.7PropertiesofTrees.........................2.1.8

Stars.................................

2.2AlgorithmsandComplexity........................

2.2.1

ComplexityClassesandNP-Completeness............

2.3On-LineAlgorithms.............................2.4VisibleVertexandVisibilityList.....................2.5VisibleEdge.................................3On-LineVertex-RankingofTrees

3.1TheAlgorithm...............................3.2CorrectnessProofandComplexityAnalysis...............3.3RankBoundsforSubclassesofTrees...................

3.3.1RankUpperBoundforStars....................3.3.2

RankUpperBoundforCompletet-aryTrees...........

4On-LineVertex-RankingofSimpleGraphs

4.1TheAlgorithm...............................

iii1415161617191920212222232525283131313333

CONTENTS

4.2CorrectnessProofandComplexityAnalysis...............5On-LineEdge-RankingofTrees

5.1TheAlgorithm...............................5.2CorrectnessProofandComplexityAnalysis...............5.3On-LineEdge-RankingofTreeswithBatchArrivalofEdges......

5.3.1Preliminaries............................5.3.2TheAlgorithm...........................5.3.3

CorrectnessProofandComplexityAnalysis...........

6ConclusionsandOpenProblemsReferences

iv363939434545495253

ListofFigures

1.1AgraphG..................................1.2Avertex-coloringofgraphG........................1.3Anedge-coloringofgraphG.........................1.4Avertex-rankingofgraphG........................1.5Anedge-rankingofgraphG.........................2.1SubgraphsinducedbyverticesandedgesofG...............2.2Agraphwiththreeconnectedcomponents.................2.3Atreewithninenodes............................2.4Acomplete3-arytree............................2.5Astarwithsevennodes...........................3.1AtreeT.

..................................

3.2(a)Anoptimalvertex-rankingofthetreeinfigure3.1.(b)Avertex-rankingofthetreeinfigure3.1producedbytheproposedon-linealgorithmforthevertexarrivalsequencev5,v2,v1,v3,v6,v7,v4,v8....

v

34458151718181926

27

LISTOFFIGURES

4.1AgraphG..................................4.2Avertex-rankingofthegraphinfigure4.1producedbytheproposed

on-linealgorithmfortheinputarrivalsequencev1,v5,v7,v2,v8,v6,v3,v4.5.1AtreeT󰀇...................................5.2(a)Anoptimaledge-rankingofthetreeinfigure5.1...........5.3(b)Anedge-rankingofthetreeinfigure5.1producedby

theproposedon-linealgorithmfortheedgearrivalsequencee5,e8,e4,e11,e1,e13,e2,e10,e9,e14,e6,e3,e12,e7...............

vi34

344040

41

Acknowledgments

WewouldliketoexpressoursinceregratitudetoourthesissupervisorDr.Md.AbulKashemMia,Professor,DepartmentofComputerScienceandEngineering,BUET.Heassignedusaninterestingandstateoftheartproblemintheoreticalcomputerscience,whichhasdiverseapplicationsintherealworld.Hissoundandthoroughknowledgeandexpertiseinalgorithms,graphtheoryandmathematicshelpedustoovercomethedifficultphasesofourdissertationwork.Wearealsothankfultohimforteachingustwointerestingcourses,theoryofcomputationandgraphtheory,whichultimatelyinspiredustodoresearchingraphalgorithms.Withouthisproperguidance,advice,criticism,encouragementandactiveparticipation,itwouldnothavebeenpossibletocompletethisthesis.

WewouldliketousethisopportunitytothankProfessorMirkoHorˇna´k,DepartmentˇarikUniversity,KoˇofGeometryandAlgebra,P.J.Saf´sice,Slovakiaforprovidinguswithamanuscriptofoneofhispaperswhichgreatlyhelpedusduringourresearch.Finally,wewouldliketothankourparentsandourfriendswhoweresupportivethroughoutourundergraduatestudies.

vii

Abstract

Avertex-rankingofagraphGisalabelingoftheverticesofGsuchthateverypathbetweentwoverticeswiththesamelabelγcontainsavertexwithlabelλ>γ.Anedge-rankingisdefinedanalogously.Inanyon-linerankingalgorithm,theverticesoredgesarriveoneatatimeinanyorderandonlythelocalinformationinthesubgraphinducedbythecurrentlyavailableverticesoredgesisavailablewhenthealgorithmmustchoosearankforthenewlyarrivedvertexoredge.Inthisthesiswepresentanon-linealgorithmtoranktheverticesofatreeTintimeO(n2),wherenisthenumberofverticesinT.Thebestknownon-linealgorithmforthisproblemtakesO(n3)time.Wealsoderiveboundsonthenumberofranksusedbythetreerankingalgorithmforsomespecialsub-classesoftrees.WethengiveanO(n·m)timeon-linealgorithmforrankingtheverticesofagraphG,wherenandmarethenumbersofverticesandedgesinG,respectively.Finallyweprovidequadratic-timeon-linealgorithmsforedge-rankingoftreesintheclassicaledge-rankingmodelandthebatcharrivalmodel.

1

Chapter1Introduction

Inthischapter,weprovidethenecessarybackground,presentstateoftheproblemsconsideredandmotivationforthisstudyregardingtherankingsofgraphs.Wealsodefinetheproblemanddelineatethescopeofthisthesis.Insection1.1,wediscussthehistoricalbackgroundofvertex-rankingandedge-rankingofgraphs.Wethendefinethevertex-rankingandedge-rankingproblems,andintroducegeneralizationsofvertex-rankingandedge-ranking,namelygeneralizedvertex(edge)-ranking(c-vertex(edge)-ranking)andon-linevertex(edge)-ranking.Section1.2discussesthescopeofthisthesis.Finallyinsection1.3,wesummarizetheresultsofthisthesisandcomparethemwiththepreviouslyachievedresults.

1.1Backgrounds

GraphtheoryhasdevelopedintoaverybroadandmaturefieldofmathematicssinceitsintroductionbyEulerinthe18thcentury.Agraphisanintuitivelypleasingandflexiblemodelfordealingwithrelationshipsbetweenobjects(real-worldormathematical),

2

CHAPTER1.INTRODUCTION3

andareusedinnumerousareasofmathematicalresearchandpracticalapplicationsintherealworld.Thetheoryofgraphsanddigraphsisadelightfulplaygroundfortheexplorationofprooftechniquesindiscreteandcombinatorialmathematics.Ithasdiverseapplicationsintherealmofcomputing,socialandnaturalsciences.Infactthelasttwodecadeshavewitnessedanupsurgeofinterestandactivityingraphtheory,particularlyamongmathematiciansandcomputerscientists.Becausemuchworkhasbeendoneonthestructureandmathematicalpropertiesongraphs,recentresearcheffortsaremainlyconcentratedondiscoveringefficientalgorithmsforvariousgraph-theoreticproblems.

AgraphG=(V,E)withnverticesandmedgesconsistsofavertexsetV={v1,v2,···,vn}andanedgesetE={e1,e2,···,em},whereanedgeinEjoinstwoverticesinV.Figure1.1depictsagraphof8verticesand12edges,whereverticesaredrawnbycircles,edgesbylines,vertexnamesnexttothecirclesandedgenamesnexttothelines.Efficientalgorithmshavebeenobtainedforvariousgraphproblems,suchascoloring,planaritytestingandmaximumflowproblems.

CHAPTER1.INTRODUCTION4

tocolortheverticesofagivengraphusingminimumnumberofcolorssothatadjacentverticesareassigneddifferentcolors.Figure1.2depictsavertex-coloringofagraphGusingthreecolors,wherecolorsareshownnexttothevertices.Thecorrespondingedge-coloringproblemistocolortheedgesofagraphwiththeminimumnumberofcolorssothatnotwoadjacentedgesreceivethesamecolor.Figure1.3depictsaedge-coloringofGusingfivecolors,wherecolorsareshownnexttotheedges.Thevertex-rankingproblemandtheedge-rankingproblemarerestrictionsofthevertex-coloringproblemandtheedge-coloringproblem,respectively.

1

133

2211Figure1.2:Avertex-coloringofgraphG.

345212521134Figure1.3:Anedge-coloringofgraphG.

CHAPTER1.INTRODUCTION5

1.1.1TheVertex-RankingProblem

Avertex-rankingofagraphG=(V,E)isapropervertex-coloringϕ:V→NsuchthateverypathinGwithend-verticesofthesamecolorγcontainsaninternalvertexwithcolor≥γ+1.Theintegercolorϕ(u)ofavertexuiscalledtherankofthevertexu.Clearly,avertex-labelingisavertex-rankingifandonlyif,foranylabeli,deletionofallverticeswithlabels>ileaves(connected)components,eachhavingatmostonevertexwithlabeli.Theminimumnumberofranksneededforavertex-rankingofGiscalledthevertex-rankingnumberofGandisdenotedbyχr(G).Avertex-rankingofGusingtheminimumnumberofranksiscalledanoptimalvertex-rankingofG.Thevertex-rankingproblemistofindanoptimalvertex-rankingofagivengraph.Thevertex-rankingproblemisarestrictionofthevertex-coloringproblem,sincetheconstraintsofvertex-rankingimplythatadjacentverticescannothavethesamerank(color).Figure1.4depictsavertex-rankingofagraphGusing5ranks,whereranksareshownnexttothevertices.

1

125

4311Figure1.4:Avertex-rankingofgraphG.

Thevertex-rankingproblem,alsoknownastheorderedcoloringproblem[17],hasbeenextensivelyinvestigatedandhasreceivedmuchattentionduetoagrowingnumberofapplicationsindiverseareas.Theproblemoffindinganoptimalvertex-rankingofa

CHAPTER1.INTRODUCTION6

graphGisequivalenttotheproblemoffindingaminimum-heightvertex-separatortreeofG.Duetothisequivalence,thevertex-rankingproblemhasanimportantapplicationintheparallelCholeskifactorizationofmatrices[7,23].Yetanotherapplicationofthevertex-rankingproblemliesinthefieldofVLSI-layout[10,22,30].

Wenowreviewtheresultsconcerningthevertex-rankingproblem.Thevertex-rankingproblemwasposedin1988byIyeretal.inrelationtoapplicationsinVLSIlayoutandinmanufacturingsystems[10].Pothenprovedthatthevertex-rankingproblemisNP-hardingeneral[2,26],andhenceitisveryunlikelythatthereisapolynomial-timealgorithmforsolvingtheproblemforgeneralgraphs[1].Henceanapproximationalgorithmwouldbeuseful.AnapproximationalgorithmforgraphsingeneralwasgivenbyBodlaenderetal.,whoseapproximationratioisO(log2n)forthevertex-rankingnumber[3].Althoughthevertex-rankingproblemisNP-hardingeneralforgraphs,Iyeretal.presentedanO(nlogn)timesequentialalgorithmtosolvethevertex-rankingproblemfortrees[10],wherenisthenumberofverticesoftheinputtree.ThenSch¨afferobtainedalinear-timealgorithmbyrefiningtheiralgorithmanditsanalysis[26].Deogunetal.gavealgorithmstosolvethevertex-rankingproblemforintervalgraphsinO(n3)timeandforpermutationgraphsinO(n6)time[5].Bodlaenderetal.presentedapolynomial-timesequentialalgorithmtosolvethevertex-rankingproblemforpartialk-trees,thatis,graphsoftreewidthboundedbyafixedintegerk[2].Kloksetal.[18]havepresentedanalgorithmforcomputingthevertex-rankingnumberofanasteroidaltriple-freegraphintimepolynomialinthenumberofverticesandthenumberofminimalseparators.NewtonandKashempresentedanefficientoptimalalgorithmforvertex-rankingofpermutationgraphsinO(n3)time[25].Sun-yuanHsiehsolvedthevertexrankingproblemofastarlikegraphinO(n)time[7].

CHAPTER1.INTRODUCTION7

1.1.2GeneralizedVertex-Rankings

Ageneralizationofthevertex-rankingproblemwasintroducedin[35].Herewedefinethec-vertex-rankingofagraphandtheworkdoneonthec-vertex-rankingproblem.

c-Vertex-Ranking

Anaturalgeneralizationofthevertex-rankingproblemisthec-vertex-ranking[35].Forapositiveintegerc,ac-vertex-rankingofagraphGisalabelingoftheverticesofGwithpositiveintegerssuchthat,foranylabelγ,deletionofallverticeswithlabels>γleaves(connected)components,eachhavingatmostcverticeswithlabelγ[35].Clearly,anordinaryvertex-rankingisa1-vertex-ranking.Thec-vertex-rankingproblemistofindac-vertex-rankingofagivengraphusingtheminimumnumberofranks.Theminimumnumberofranksneededforac-vertex-rankingofGiscalledthec-vertex-rankingnumber.TheproblemisNP-hardingeneral,sincetheordinaryvertex-rankingproblemisNP-hard[2,26].Zhouetal.haveobtainedalinear-timesequentialalgorithmtosolvethec-vertex-rankingproblemfortrees[35].Kashemetal.havepresentedapolynomial-timesequentialalgorithmforthec-vertex-rankingofpartialk-trees[14].RecentlyKashemetal.havepresentedanoptimalparallelalgorithmtosolvethec-vertex-rankingproblemontreesforanypositiveintegercintimeO(log2n)usinglinearoperationsontheEREWPRAMmodel[12].

1.1.3TheEdge-RankingProblem

Theedge-rankingproblemisdefinedanalogouslyasforthevertex-rankingproblem.Anedge-rankingofagraphGisalabelingoftheedgesofGwithpositiveintegerssuchthateverypathbetweentwoedgeswiththesamelabelicontainsanedgewithlabel

CHAPTER1.INTRODUCTION8

j>i[9,6].Clearly,anedge-labelingisanedge-rankingifandonlyif,foranylabeli,deletionofalledgeswithlabels>ileaves(connected)components,eachhavingatmostoneedgewithlabeli.Theminimumnumberofranksneededforanedge-rankingofGiscalledtheedge-rankingnumberofGandisdenotedbyχ󰀇r(G).Anedge-rankingofGusingtheminimumnumberofranksiscalledanoptimaledge-rankingofG.Theedge-rankingproblemistofindanoptimaledge-rankingofagivengraph.Theconstraintsfortheedge-rankingproblemimplythattwoadjacentedgescannothavethesamerank.Thustheedge-rankingproblemisarestrictionoftheedge-coloringproblem.Figure1.5depictsanedge-rankingofagraphusing7ranks,whereranksareshownnexttotheedges.

2131512371Figure1.5:Anedge-rankingofgraphG.

Theproblemoffindinganoptimaledge-rankingofagraphGhasapplicationsinschedulingtheparallelassemblyofacomplexmulti-partproductfromitscomponents.Theedge-rankingproblemforagraphGisalsoequivalenttofindinganedge-separatortreeofGhavingtheminimumheight.Anedge-separatortreewithminimumheightcorrespondstoaparallelcomputationschemehavingtheminimumcomputationtime[24].

Wenextreviewtheresultsontheedge-rankingproblem.Theproblemoffindinganoptimaledge-rankingwasfirststudiedbyIyeretal.in1991astheyfoundthatthe

CHAPTER1.INTRODUCTION9

problemhasanapplicationinschedulingtheparallelassemblyofmulti-partproducts.TheygaveanO(nlogn)timeapproximationalgorithmforfindinganedge-rankingoftreesTusingatmosttwicetheminimumnumberofranks,wherenisthenumberofverticesinT[9].Theirapproximationalgorithmusesthevertex-rankingalgorithmin[10]asasubroutine.Themainopenproblemintheirpaperistodeterminewhethertheedge-rankingproblemisinPorinNP-hard.LaterTorreetal.gaveanexactalgorithmtosolvetheedge-rankingproblemfortreesintimeO(n3logn)bymeansofatwo-layeredgreedymethod[31].Thustheedge-rankingproblemwhenrestrictedtotreesisinP.However,LamandYuehaveprovedthattheedge-rankingproblemisNP-hardforgraphsingeneral[20].Theyhavealsosolvedtheoptimaledge-rankingproblemontreesinlinear-time[19].

1.1.4GeneralizedEdge-Rankings

Anaturalgeneralizationofanordinaryedge-rankingisthec-edge-ranking[34].Ac-edge-rankingofagraphG,forapositiveintegerc,isalabelingoftheedgesofGwithpositiveintegerssuchthat,foranylabeli,deletionofalledgeswithlabels>ileaves(connected)components,eachhavingatmostcedgeswithlabeli.Clearly,anordinaryedge-rankingisa1-edge-ranking.Theminimumnumberofranksneededforac-edge-rankingofGiscalledthec-edge-rankingnumber.Ac-edge-rankingofGusingminimumnumberofranksiscalledanoptimalc-edge-rankingofG.Thec-edge-rankingproblemistofindanoptimalc-edge-rankingofagivengraphG.Zhouetal.gaveanalgorithmtofindanoptimalc-edge-rankingofagiventreeT,foranypositiveintegerc,intimeO(n2log∆),wherenand∆arethenumberofverticesandthemaximumvertex-degreeofT,respectively[34].Kashemetal.gaveapolynomialtimesequentialalgorithmforgeneralizededge-rankingofpartialk-treeswithbounded

CHAPTER1.INTRODUCTIONmaximumdegree[15].

10

1.1.5On-LineRankingsofGraphs

Inthissection,wediscusstheon-lineversionofranking,i.e.on-linerankingsofgraphs.Theon-linerankingproblemwasfirstraisedin[32].Intheon-linemodel,thevertices(edges)oftheinputgraphGarriveonebyoneinanunrestrictedorder.Theinputsequenceofthevertices(edges),denotedbyv1,v2,v3,...(e1,e2,e3,...),indicatestheactualorderofarrivalbyincreasingsubscripts.Intheithstep(iteration),onlythesubgraphinducedbythecurrentlyavailablevertices(edges)isknown(withoutanyinformationonthepositionofthissubgraphinG),andacolor(rank)hastobeassignedtovi(ei).Theassignedcolorscannotbealteredlater.

On-linerankingisarelativelynewareaofresearchwithfewmentionableresults.Muchworkremainstobedoneinthisfield.Wenowmentiontheresultsinthisareathatdeserveattention.ThefirstsignificantworkonthisproblemwasdonebySchiermeyeretal.Theycharacterizedtheclassofgraphsforwhichon-linevertex-rankingcanbefoundusingonlythreeranks[29].Theyalsoprovedthatforn≥2,thegreedyfirst-fitcoloringheuristiccanrankann-vertexpathusingamaximumof3log2nranks,independentlyfromthearrivingorderofvertices.Bruothetal.improvedthisresultbyshowingthatthemaximumnumberofranksrequiredforon-linerankingtheverticesofann-vertexpathis2󰀘log2n󰀙+1,wheren≥2[4].Theyalsoobtainedasimilarboundforcycles.Howevernoneofthesetwopapersprovideefficienton-linealgorithmsforvertex-rankingofgraphs.Leeetal.gavethefirston-linevertex-rankingalgorithmfortreesthatrunsinO(n3)time[21].

CHAPTER1.INTRODUCTION11

1.2ScopeofthisThesis

Inthisthesis,wehaveinvestigatedon-linealgorithmsforrankingtheverticesandedgesofagraph.WeshowthattheverticesofatreeTcanberankedusinganon-linealgorithminO(n2)time,wherenisthenumberofverticesinT.ThepreviousbestknownalgorithmforthisproblemtookO(n3)time[21].Weanalyzetheperformanceofourtreerankingalgorithmbyderivingupperboundsonthenumberofranksusedbythealgorithmfortwoimportantsub-classesoftrees,namelystarsandcompletet-arytrees.Wethenprovideforthefirsttimeanon-linealgorithmforvertex-rankingasimplegraphGinO(n·m)time,wherenisthenumberofverticesandmisthenumberofedgesinG.Ouralgorithmsutilizesthegreedycoloringstrategy,i.e.ateachiterationofthealgorithm,thenewlyarrivedvertexisranked(colored)withtheleastpossiblecolorwithoutviolatingtherankingproperty.Finally,wegiveforthefirsttimeon-linepolynomial-timealgorithmsforedge-rankingsoftreesintheclassicalon-lineedge-rankingmodelandthebatcharrivalmodel.

1.3Summary

Wenowsummarizetheresultsofthisthesis.Themainresultsofthisthesiscanbedividedintothreeparts.Inthefirstpart,wegiveanon-linealgorithmforrankingtheverticesofatreeinquadratic-time.Thetime-complexityofouralgorithmisanimprovementoverthepreviousbestknownalgorithm[21].Inthesecondpart,weprovideanefficientpolynomial-timeon-linealgorithmforthevertex-rankingofasimplegraph.Inthethirdpartweshowthattheedgesofatreecanberankedinquadratic-timebyanon-linealgorithm.Wealsoprovideinthethirdpartaquadratic-timeon-line

CHAPTER1.INTRODUCTION

algorithmforrankingtheedgesofatreewhentheedgesarriveinbatches.Thethesisisorganizedasfollows.

12

Inchapter2,weprovidepreliminary

mathematicaldefinitionsconcerninggraphsandalgorithmsingeneral.Chapter3givesanO(n2)timeon-linealgorithmsforvertex-rankingofatree.Inchapter4wepresentapolynomial-timeon-linealgorithmforvertex-rankingofasimplegraph.Inchapter5wegivequadratictimeon-linealgorithmsforrankingtheedgesofatreeintheclassicaledge-rankingmodelandthealternativebatcharrivalmodel.Finally,chapter6concludeswithadiscussionoftheresultsandfutureworks.

Chapter2Preliminaries

Inthischapterwedefinesomebasictermsofgraphtheory,algorithmsandcomputationalcomplexity.Definitionsnotincludedinthischapterwillbeintroducedastheyareneeded.Westart,in2.1,byprovidingsomedefinitionsofstandardgraph-theoretictermsusedthroughoutthisthesis.Section2.2introducesthebasicideaofpolynomial-timealgorithms,variouscomplexityclassesanddefinesthenotionofNP-completeness.In2.3wediscusstheconceptofon-linealgorithms.FinallyInthelasttwosections(2.4,2.5)weintroducetheimportantconceptsofvisiblerank,visiblevertex,visibleedgeandvisibilitylist.

2.1BasicTerminology

Inthissectionwegivedefinitionsofstandardgraph-theoretictermsusedthroughoutthisthesis.Foramorethoroughtreatmentofgraphtheory,wereferto[33].

13

CHAPTER2.PRELIMINARIES14

2.1.1GraphsandMultigraphs

AgraphGisastructure(V,E)whichconsistsofasetofverticesVandasetofedgesE;eachedgeisanunorderedpairofvertices(seeFigure1.1).Agraphisfiniteifitsvertexsetandedgesetarefinite.Everygraphmentionedinthisthesisisfinite,unlessexplicitlymentionedotherwise.WedenotethesetofverticesofGbyV(G)andthesetofedgesbyE(G).ThroughoutthisthesisthenumberofverticesofGisdenotedbyn,thatis,n=|V|,andthenumberofedgesofGisdenotedbym,thatis,m=|E|.SoforthegraphinFigure1.1n=8andm=12.Ife=(u,v)isanedge,theneissaidtojointheverticesuandv,andtheseverticesarethensaidtobeadjacent.Inthiscasewealsosaythatuandvareneighbors,andthateisincidenttouandv.Multipleedgesareedgeshavingthesamepairofend-points,whilealoopjoinsavertextoitself.Thegraphinwhichloopsandmultipleedgesareallowediscalledamultigraph.IfagraphGhasnomultipleedgesorloops,thenGissaidtobeasimplegraph.Sometimesasimplegraphissimplycalledagraphifthereisnodangerofconfusion.IntheremainderofthisthesisitisassumedthatGisasimplegraph.

2.1.2DegreeofaVertex

ThedegreeofavertexvinagraphGisthenumberofedgesincidenttov,andisdenotedbydG(v)orsimplybyd(v).TheminimumandmaximumdegreesofverticesofGaredenotedbyδ(G)and∆(G),respectively.ForthegraphinFigure1.1d(v2)=4becausethe4edgese2,e3,e6ande5areincidenttov2andalso,δ(G)=2and∆(G)=5.Thefollowingtheorem,sometimescalledthe”HandshakingLemma”willbeusedinthecomplexityanalysisofourgraphrankingalgorithm.Theorem2.1.1IfG=(V,E)isagraphand|E|=m,then

󰀂

d(v)=2m.

v∈V(G)

CHAPTER2.PRELIMINARIESProof.

15

(ProofbyCounting)Summingthedegreescountseachedgetwice,because

eachedgehastwoendpointsandtheedgecontributestothedegreesumonceforeachendpoint.

2

2.1.3Subgraphs

AsubgraphofagraphG=(V,E)isagraphG󰀇=(V󰀇,E󰀇)suchthatV󰀇⊆VandE󰀇⊆E;wedenotethisasG󰀇⊆G.IfG󰀇containsalltheedgesofGthatjointwoverticesinV󰀇,thenG󰀇issaidtobethesubgraphinducedbyV󰀇,andisdenotedbyG[V󰀇].IfV󰀇consistsofexactlytheverticesofGonwhichedgesinE󰀇areincident,thenG󰀇issaidtobethesubgraphinducedbyE󰀇,andisdenotedbyG[E󰀇].Figure2.1(a)depictsasubgraphofGinFigure1.1inducedby{v1,v2,v7,v8}andFigure2.1(b)depictsasubgraphinducedby{e7,e9,e10,e11,e12}.

CHAPTER2.PRELIMINARIES16

ofV,thenG−V󰀇isthesubgraphofGobtainedbydeletingtheverticesinV󰀇andalltheedgesincidenttothem.ThenG−V󰀇isasubgraphofGinducedbyV−V󰀇.Similarly,ifeisanedgeofG,thenG−eisthesubgraphofGobtainedbydeletingtheedgee.Moregenerally,ifE󰀇⊆E,thenG−E󰀇isthesubgraphofGobtainedbydeletingtheedgesinE󰀇.

2.1.4PathsandCycles

Av0−vlwalkinGisanalternatingsequenceofverticesandedgesofG,v0,e1,v1,...,vl−1,el,vl,beginningandendingwithavertex,inwhicheachedgeisincidenttotwoverticesimmediatelyprecedingandfollowingit.

Ifthevertices

v0,v1,...,vl−1,vlaredistinct,thenthewalkiscalledapathandisdenotedbyv0v1···vl.Thelengthofthepathisl,onelessthanthenumberofverticesonthepath.Awalkv0,e1,v1,...,vl−1,el,vlisclosedifv0=vl.Aclosedwalkhavingdistinctverticesandcontainingatleastoneedgeiscalledacycle.InFigure1.1,v1,e2,v2,e6,v6,e7,v3,e5,v2,e3,v7isanexampleofawalkandv1v2v7v8isacyclewithfourvertices.

2.1.5ComponentsofaGraph

AgraphGisconnectedifforeverypairofdistinctvertices{u,v},thereisapathinGbetweenuandv.A(connected)componentofagraphisamaximalconnectedsubgraph.Adisconnectedgraphisagraphwhichisnotconnected.Figure2.2showsadisconnectedgraphwiththree(connected)components.

CHAPTER2.PRELIMINARIES

v1v2

v5v6

v4

v8

v3

v7v9

17

Figure2.2:Agraphwiththreeconnectedcomponents.

2.1.6Trees

Atreeisaconnectedacyclicgraph.Figure2.3isanexampleofatree.Theverticesofatreearegenerallytermedasnodesofthetree.Arootedtreeisatreeinwhichaparticularnodeisdistinguishedfromtheothers.Thedistinguishednodeiscalledtherootofthetree.InFigure2.3,v1istheroot.Therootofatreeisgenerallydrawnatthetop.Everynodevotherthantherootisconnectedbyanedgetosomeothernodepcalledtheparentofu.Inthatcase,uiscalledachildofp.Usuallytheparentofanodeisdrawnabovethatnode.InFigure2.3,v1istheparentofv3andv7isachildofv4.Aleafisanodewithoutanychildren.Aninternalnodeisanodewithat-leastonechild.Soeverynodeofatreeiseitheraleaforaninternalnode,butnotboth.InFigure2.3,theleavesarev5,v6,v3,v9,andv8.Theinternalnodesarev1,v2,v4,andv7.

Theparent-childrelationshipcanbenaturallyextendedtoancestorsanddescendants.Supposeu1,u2,...,ulisasequenceofnodesinatreesuchthatuiistheparentofui+1,fori=1,2,...,l−1.Thennodeu1iscalledanancestorofulandnodeuladescendantofu1.Therootisanancestorofeverynodeandeverynodeisadescendantoftheroot.

InatreeT,anodeutogetherwithallofitsdescendants,ifany,iscalledasubtree

CHAPTER2.PRELIMINARIES

v1v2v3v418

v5v6v7v9v8

Figure2.3:Atreewithninenodes.

ofT.ReferringtoFigure2.3,nodesv2,v5andv6formasubtreerootedatv2.ThesubtreeofTrootedatavertexu∈V(T)isdenotedbyT(u).

Theheightofarootedtreeisthelengthofthelongestpathfromtheroot.Inarootedtree,thedepthorlevelofanodeuisitsdistancefromtheroot,thatis,thelengthoftheuniquepathfromtheroottou.InFigure2.3,nodev7isofdepth2.ThetreeinFigure2.3hasheight3.

Arootedtreeiscalledat-arytreeifeveryinternalnodehasnomorethantchildren.Thetreeiscalledafullt-arytreeifeveryinternalnodehasexactlytchildren.Ant-arytreewitht=2iscalledabinarytree.Acompletet-arytreeisafullt-arytreewhereeveryleafisatthesamelevel.Figure2.4showsacomplete3-arytreeofheight2.

CHAPTER2.PRELIMINARIES19

2.1.7PropertiesofTrees

Thefollowingresultsconcerningthepropertiesoftreeswillbeusedthroughoutthethesis.Theproofoftheseresultscanbefoundinanystandarddiscretemathematicstext[27].

Theorem2.1.2Atreewithnverticeshasn−1edges.

Theorem2.1.3Thereareatmostthleavesinant-arytreeofheighth.Acompletet-arytreehasexactlythleaves.

Theorem2.1.4Theheightofacompletet-arytreeish=logt[1+(t−1)n]−1,wherenisthenumberofverticesofthetree.

2.1.8Stars

Astarofnverticesisatreewhereonevertexhasdegreen−1andalltheremainingn−1verticeshavedegree1.Thevertexwithdegreen−1iscalledthecenterofthestar.AstarisusuallydenotedasKn−1,1.Figure2.5depictsastarwithsevennodes.v1isthecenterofthestar.

CHAPTER2.PRELIMINARIES20

2.2AlgorithmsandComplexity

Inthissectionwebrieflyintroducesometerminologyrelatedtothecomplexityanalysisofalgorithms.

Forinterestedreaders,werefertoGareyandJohnson[8].

The

complexityofanalgorithmisdeterminedbytheamountofresources(spaceandtime)necessarytoexecuteit.Themostwidelyusedcomplexitymeasureforanalgorithmistherunningtimeofthealgorithm,whichisexpressedasthenumberofoperationsitperformsbeforeproducingthefinaloutputofthealgorithm.Thenumberofoperationsrequiredbyanalgorithmisnotthesameforallprobleminstances.Thusallinputinstancesofagivensizeareconsideredtogether,andthecomplexityofanalgorithmforthatinputsizeisdefinedastheworstcasebehaviorofthealgorithmonanyoftheseinputs.Thereforetherunningtimeofanalgorithmisafunctionoftheinputsizenofthealgorithm.

Inanalyzingthecomputationalcomplexityofanalgorithm,wearemainlyconcernedwiththeasymptoticbehavior,thatis,thebehaviorofthealgorithmwhensubjectedtoverylargeinputs.Todealwithsuchasymptoticrunningtimeanalysis,weintroducethefollowingnotations.Letf(n)andg(n)befunctionsfromthepositiveintegerstothepositiverealsandletf(n)bethetimecomplexityorrunningtimeofthealgorithm,wherenistheinputsize.Thenwewritef(n)=O(g(n))ifthereexistspositiveconstantscandn0suchthatf(n)≤c·g(n)foralln>n0.Wethensaythattherunningtimeofthealgorithmisboundedbyg(n).Forexampleifg(n)=n,wecansaythattherunningtimeofthealgorithmisboundedbyO(n)andthealgorithmissaidtobealinear-timealgorithm.Ingeneralifg(n)isapolynomialfunctionofn,thenthealgorithmiscalledapolynomial-timealgorithm.

CHAPTER2.PRELIMINARIES21

2.2.1ComplexityClassesandNP-Completeness

Wenowdefinesomeimportantcomplexityclasses.TheclassPconsistsofallthosedecisionproblemsthatcanbesolvedonadeterministicsequentialmachineinanamountoftimethatispolynomialinthesizeoftheinput;theclassNPconsistsofallthoseproblemswhosepositivesolutionscanbeverifiedinpolynomialtimegiventherightinformation,orequivalently,whosesolutioncanbefoundinpolynomialtimeonanon-deterministicmachine.AnyprobleminPisalsoinNP,sinceifaproblemisinPthenwecanverifyit’ssolutioninpolynomialtime.

Here,wearemainlyinterestedinanotherclassofproblems,calledNP-completeproblems(orNPC),whichcanbelooselydescribedasthehardestproblemsinNPandthereforetheyaretheleastlikelytobeinP.Nopolynomial-timealgorithmhasyetbeendiscoveredforanNP-completeproblem,norhasanyoneyetbeenabletoprovethatnopolynomial-timealgorithmcanexistforanyofthem.

Moreprecisely,adecisionproblemCisNP-completeifitiscompleteforNP,meaningthat:(1)itisinNP,and

(2)itisNP-hard,i.e.everyotherprobleminNPispolynomial-timereducibleto

it.

“Polynomial-timereducible”heremeansthatforeveryproblemL,thereisapolynomial-timemany-onereduction,adeterministicalgorithmwhichtransformsinstancesl∈Lintoinstancesc∈C,suchthattheanswertocisYESifandonlyiftheanswertolisYES.ToprovethatanNPproblemAisinfactanNP-completeproblemitissufficienttoshowthatanalreadyknownNP-completeproblemreduces

CHAPTER2.PRELIMINARIES22

toA.Aconsequenceofthisdefinitionisthatifwehadapolynomial-timealgorithmforC,wecouldsolveallproblemsinNPinpolynomialtime.

2.3On-LineAlgorithms

Analgorithmiscalledoff-lineifallinputdatamustbeaccessedbeforetheoutputisproduced.Mostresearchdoneingraphtheoryconcentratesonoff-linealgorithms.Onthecontrary,anon-linealgorithmhastomake(partial)decisionsafterseeingonlyasubsetoftheinput.Forexample,forranking(coloring)problems,therearetwonaturalon-linemodels:theinputisgiveneithervertex-by-vertexoredge-by-edge.Thealgorithmassignsarank(color)tothecurrentvertexoredgebasedonlyonpasthistoryandarank(color)assignedtoavertexoredgecannotbechangedlater.Inanon-linerankingmodel,sincethevertices(edges)arriveoneatatimeineachiteration,onlypartialorincompleteinformationabouttheinputgraphisavailableateachstep.Soitisnotpossibletoguaranteethatanon-linealgorithmcanrankthevertices(edges)ofagraphwiththeminimumnumberofranks.Thereforemoston-lineranking(coloring)algorithmsuseagreedystrategytorankthenewlyarrivedvertex(edge)ineachiterationwiththeleastpossiblerankwithoutviolatingthevertex(edge)-rankingproperty.

2.4VisibleVertexandVisibilityList

Letvibethenewlyarrivedvertexattheithiterationofanon-linealgorithm.Theneighborsofviin{v1,...,vi−1}arecalledthecurrentneighborsofvi.WedenoteGiasthesubgraphofGinducedby{v1,...,vi}.LetC(vi)bethe(connected)component

CHAPTER2.PRELIMINARIES23

ofGiwhichcontainsvi,thenewlyarrivedvertex.OnlyC(vi)willbeconsideredwhilerankingvi,sincetheverticesinothercomponentswillnotaffecttheranksofverticesinC(vi).Alsoforallverticesu,v∈V(G),wedenotethesetofalldistinctpathsbetweenuandvbyP(u,v).

Letϕbeavertex-labelingofagraphGwithpositiveintegers.Wedenotetherank(label)ofavertexubyϕ(u).TheconceptsofvisiblerankandvisibilitylistwereintroducedbyIyeretal.[10].Consideranyvertexu∈V(C(vi))\\{vi}.Therankϕ(u)ofuissaidtobevisiblefromviunderϕvisiblefromviunderϕifthereexistsapathP∈P(vi,u)suchthatalltheinternalverticesinPhaveranks≤ϕ(u).Suchavertexuisthencalledavisiblevertex.Thelistofallranksvisiblefromviunderϕiscalledthevisibilitylistofvi,andisdenotedbyL(vi).SoL(vi)canbewritteninthefollowingform

L(vi)={ϕ(u)|u∈V(C(vi))\\{vi}andϕ(u)isvisiblefromvi}.

L(vi)willingeneralbeamulti-set,whereanelementγinL(vi)canappearmorethanonceifandonlyifγistherankofmorethanonevisiblevertex.Arankthatisnotvisiblefromviunderϕiscalledaninvisiblerank.Foranyintegerγwedenotebycount(L(vi),γ)thenumberofγ’scontainedinL(vi)[35].WedenotethelargestrankinL(vi)bymax{L(vi)}.IfL(vi)=∅,thenweassumethatmax{L(vi)}=0.

2.5VisibleEdge

LetT=(V,E)beatree.Foranytwoedgese,e󰀇∈E(T),wedenotetheuniquepathfrometoe󰀇byP(e,e󰀇).TheuniquepathfromavertexvtoanedgeeisdenotedbyP(v,e).

Leteibethenewlyarrivededgeattheithiterationofanon-linealgorithm.

CHAPTER2.PRELIMINARIES24

WedenoteTiasthesubgraphofTinducedby{e1,e2,...,ei}.LetT(ei)bethe(connected)componentofTiwhichcontainsei,thenewlyarrivededge.OnlyT(ei)willbeconsideredwhilerankingei,sincetheedgesinothercomponentswillnotaffecttheranksofedgesinT(ei).

Letϕbeanedge-labelingofagraphGwithpositiveintegers.Wedenotetherank(label)ofanedgeebyϕ(e).Consideranyedgee∈E(T(ei))\\{ei}.Therankϕ(e)ofeissaidtobevisiblefromavertexv∈V(T(ei))underϕ,ifalltheedgesonP(v,e)arelabeledandhaveranks≤ϕ(e).Suchanedgeeisthencalledavisibleedge.Thelistofallranksvisiblefromavertexvunderϕiscalledthevisibilitylistofv,andisdenotedbyL(v).Letei=(u,v),andletL(ei)=L(u)∪L(v).ThenwesaythatL(ei)isthevisibilitylistofei.ThelistL(ei)willgenerallybeamulti-set,whereanelementγinL(ei)canappearmorethanonce.Arankthatisnotvisiblefromanendpointofeiunderϕiscalledaninvisiblerank.Foranyintegerγwedenotebycount(L(ei),γ)thenumberofγ’scontainedinL(ei)[35].

Chapter3

On-LineVertex-RankingofTrees

Inthischapterwedescribeanon-linealgorithmforrankingtheverticesofatree.In3.1wedelineatethemainideaofthealgorithmandpresentthepseudo-codeofthealgorithm.Thealgorithmisbasedontheconceptofvisiblevertexandvisibilitylistwhichareexplainedinchapter2.Weprovethecorrectnessandderivethetimecomplexityofthealgorithminsection3.2.Weendthechapterbyderivingboundsonthenumberofranksusedbythetreerankingalgorithmforsomespecialsub-classesoftrees.InthischapterwedenotetheinputgraphwhichisatreebyT.Sincethereisauniquepathbetweenanytwoverticesinatree,wehave|P(u,v)|=1foranyu,v∈V(T).LetP(u,v)={P(u,v)}.SoP(u,v)istheuniquepathbetweenuandv.

3.1TheAlgorithm

Thefirstimportantresultofourthesisisthefollowingtheorem.

Theorem3.1.1TheverticesofatreeTcanberankedusinganon-linealgorithminO(n2)time,wherenisthenumberofverticesinT.

25

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES26

Intheremainderofthissectionwegiveanon-linealgorithmforrankingtheverticesofatreeTintimeO(n2).Itisbasedonthegreedyfirst-fitcoloringheuristic.Ateachiteration,thenewlyarrivedvertexisranked(colored)withtheleastpossiblerank(color)withoutviolatingthevertex-rankingproperty.Attheithiteration,thealgorithmtakesasinputthenewlyarrivedvertexviandalistofitsneighborsin{v1,...,vi−1}.Wethenrankviwiththeleastpossiblerank.Todothat,weconstructthevisibilitylistL(vi)forvibysearchinginC(vi)tofindallvisibleranks.Thesearchiscarriedoutbyarecursivedepthfirstsearchtraversal.Duringthesearch,wekeeptrackofthelargestrankonapathstartingfromviseensofar.Asthetraversalcontinuesalonganypathfromaneighborofvi,ifavertexistraversedthathasarankgreaterthanthecurrentmaximum,thenthatrankisaddedtoL(vi)andthelargestrankisupdated.Sinceanyneighborofviistriviallyvisiblefromviunderϕ,itsrankmustbelongtoL(vi).Toincorporatethiscaseintothealgorithm,thelargestrankissetto0atthebeginningofthesearch.Asaresultwhenaneighborwofviistraversed,itsrankϕ(w)willbetriviallygreaterthan0andaddedtoL(vi).Figure3.2(a)showstheoptimalrankingofthetreeinfigure3.1using3labels,whereasfigure3.2(b)depictsarankingofthetreeproducedbyourtreerankingalgorithmusing4ranks.

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES

3127

222123411

1(a)

11

11(b)

Figure3.2:(a)Anoptimalvertex-rankingofthetreeinfigure3.1.(b)Avertex-rankingofthetreeinfigure3.1producedbytheproposedon-linealgorithmforthevertexarrivalsequencev5,v2,v1,v3,v6,v7,v4,v8.

Oncevihasbeenproperlyranked,wediscarditsvisibilitylistL(vi).Inourapproach,thevisibilitylistisavolatiledatastructure,thatis,wedonotsavethevisibilitylistofavertextobeusedlaterforrankingthenextnewvertex.Instead,wheneveranewvertexarrives,wenewlybuildthevisibilitylistforitbysearchingtheentiresubtreecontainingthenewvertex.Inthepreviouslybestknownon-linealgorithmduetoLeeetal.[21]forrankingtheverticesofatree,alistwasmaintainedforeachvertexofthetreeandallthelistswereupdatedwheneveranynewvertexwasranked.Ouron-linealgorithmavoidstheextraupdatingcostthatwouldincurifwesavedthevisibilitylistforeachvertex.Thusouron-linealgorithmrunsfasterthantheon-linealgorithmbyLeeetal.[21]forrankingtheverticesofatree.Thepseudocodeofthealgorithmisgivenbelow.Algorithm1Online

1:2:3:

Tree

fori=1tondo󰀵n=|V(T)|

readanewnodeviandtheneighborsofviin{v1,...,vi−1};letU={u1,...,um}bethesetofneighborsofviin{v1,...,vi−1};

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES

4:5:6:

28

L:=∅;

RankTree(vi,U);endfor

󰀵CurrentlyListhevisibilitylistofvi,thatisL=L(vi)

ProcedureRankTree(v,U)

1:2:3:4:

forj=1tomdo󰀵m=|U|

BuildVisibleListTree(v,uj,0);endfor

findminimumαsuchthatα∈/Landcount(L,β)≤1,foreachβsatisfyingα+1≤β≤max{L};

5:

ϕ(v):=α;󰀵rankvwithα

ProcedureBuildVisibleListTree(v,u,rmax)

1:2:3:4:5:6:7:8:9:

ifϕ(u)>rmaxthenL:=L∪{ϕ(u)};endif

letN(u)bethesetofneighborsofuinC(vi);if(N(u)\\{v})=∅thenforeachw∈N(u)\\{v}do

BuildVisibleListTree(u,w,max{rmax,ϕ(u)});endforendif

3.2CorrectnessProofandComplexityAnalysis

InthissectionweprovethecorrectnessofAlgorithm1andderiveitstime-complexity.

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES29

Wheni=1,thatis,whenthefirstvertexv1arrives,itdoesnothaveanycurrentneighbor,andsoitcanbetriviallyrankedwith1withoutviolatingthevertex-rankingproperty.Wheni>1,weinductivelyassumethattheverticesv1,...,vi−1havebeenproperlyrankedinthepreviousi−1iterations.Wenowprovethatviisproperlyrankedattheithiteration.Firstweprovethatthevisibilitylistiscorrectlyconstructedattheithiterationofthealgorithm.Wehavethefollowinglemma.

Lemma3.2.1Letvi∈V(T)bethenewlyarrivedvertexattheithiteration,andletLbethelistconstructedbyAlgorithm1forthevertexvi.ThenL=L(vi),thatis,(i)Lcontainsalltheranksvisiblefromviunderϕ;and(ii)Ldoesnotcontainanyrankinvisiblefromviunderϕ.

Proof.(i)Foracontradiction,assumethatγisarankvisiblefromviunderϕ

butγ∈/L.Letubeavisiblevertexwithrankϕ(u)=γ,whereu∈V(C(vi))\\{vi}.LetP(vi,u)betheuniquepathfromvitou.LetwbetheneighborofvionP(vi,u).Sinceγisvisiblefromvi,alltheverticesfromwtouhaveranks≤γ.Sinceϕisavertex-ranking,wehaveϕ(v)<γforallinternalverticesvonP(vi,u).ThusthelargestrankseensofarfromwtotheneighborofuonP(vi,u)is<γ.SowhenuwillbetraversedonP(vi,u),wehaveϕ(u)=γ>rmax.SoγmustbeaddedtoL.Thiscontradictsγ∈/L.ThusLcontainsalltheranksvisiblefromvi.

(ii)Foracontradiction,assumethatLcontainsarankγthatisinvisiblefromviunderϕ.Letubeavertexwithϕ(u)=γ.ConsidertheuniquepathP(vi,u)fromvitouandletwbetheneighborofvionP(vi,u).Sinceγisinvisiblefromvi,theremustbeavertexzonP(vi,u)inbetweenviandusuchthatϕ(z)>γ.AtanyvertexonP(vi,u)traversedafterz,wehavermax≥ϕ(z).SinceuistraversedafterzonP(vi,u),

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES30

atu,wehavermax≥ϕ(z)andϕ(z)>γ.Thereforeatu,wehavermax>ϕ(u).Soϕ(u)=γcannotbeaddedtoL.SoLcannotcontainanyinvisiblerank.

2

Nextweshowthattherankchosenforvi,thecurrentnewvertex,doesnotviolatethevertex-rankingpropertyinC(vi).

Lemma3.2.2Therankαproperlyranksthenewlyarrivedvertexvi∈V(T)attheithiteration.

Proof.Foracontradiction,assumethatαdoesnotproperlyrankvi.SoC(vi)will

containapathP(x,y)forsomex,y∈V(C(vi))suchthatvi∈V(P(x,y)),ϕ(x)=ϕ(y)=γ,andϕ(v)≤γforallverticesv∈V(P(x,y)).Thenϕ(vi)=α≤γandbothϕ(x)andϕ(y)arevisiblefromviunderϕ.Socount(L(vi),γ)≥2.Asα∈/L(vi),α=γisnotpossible.Thusγ≥α+1.ButaccordingtoAlgorithm1,count(L(vi),β)≤1,foreachβsatisfyingα+1≤β≤max{L}.Soαproperlyranksvi.

2

ProofofTheorem3.1.1:TheprocedureBuildVisibleListTreeiscalledexactlyonceforeachvertexv∈V(C(vi))\\{vi}foreachexecutionofRankTree.DuringanexecutionofBuildVisibleListTree,thelooponLines6-8isexecutedatmostd(v)times.

󰀂

SothetotalcostofalltheBuildVisibleListTreeprocedurecallsisv∈V(C(vi))\\{vi}d(v)=O(ec)=O(e)=O(n),whereecisthenumberofedgesinC(vi).SincethesizeofthevisibilitylistisO(|V(C(vi))|)=O(n),searchinginL(vi)tofindtherankαinLine4ofprocedureRankTreetakesO(n)time.SowecansaythattheRankTreeproceduretakestimeO(n).SincetheprocedureRankTreeiscalledforeachnewlyarrivedvertex,andthenverticesv1,...,vnarriveoneatatime,thetotaltimecomplexityofAlgorithm1󰀂

isv∈V(T)O(n)=O(n2).2

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES31

3.3RankBoundsforSubclassesofTrees

Agraphwithnverticescanberankedusingamaximumofnranks,sinceusingdifferentlabelsforeachvertexwillcreateavalid(feasible)ranking.WenowderivethemaximumranksusedbyAlgorithm1fortwospecialsubclassesoftrees,namelystarsandcompletet-arytreeswheret≥2.

3.3.1RankUpperBoundforStars

AstarwithnverticesisdenotedbyK1,n−1.Nowconsiderainputsequencewherethevertexwithdegreen−1arrivesfirstandtheremainingverticesarrivelaterinanyorder.Sincethefirstvertexhasnocurrentneighborwhenitarrives,itisassignedrank1byAlgorithm1.Theremainingverticesarrivinglaterwillhavethefirstvertex(withrank1)asacurrentneighborandthereforewillbeassignedarankthatisdifferentfromallpreviouslyassignedranksinordertomaintainthevertex-rankingproperty.Soforthisworstcaseinputsequenceforastar,themaximumrankisn.

3.3.2RankUpperBoundforCompletet-aryTrees

Therankboundforacompletet-arytreeisdelineatedinthefollowingtheorem.

Theorem3.3.1Algorithm1ranksacompletet-arytreewithatmostlogtn+c(n−1)+1labels,wherec=1−1/tand1/2≤c<1.

Inordertodeterminearankboundforacompletet-arytree,wheret≥2,wehavetoidentifytheworstcaseinputsequenceforwhichthealgorithmproducesarankingwiththemaximumnumberofranks.Lethbetheheightofacompletet-arytreeTt.

CHAPTER3.ON-LINEVERTEX-RANKINGOFTREES32

ThesetofleavesofTtisdenotedbyLandthesetofallinternalnodeatleveliis

󰀁h−1󰀁h

t

denotedbyIi.SoV(T)=(i=0Ii)∪L=i=0Ii,sinceL=Ih.AlsoI0={r},whereristherootofTt.Wehave|Ii|=ti,i=0,1,...,h.LetB(n,t)=logtn+c(n−1)+1.Wehavethefollowinglemma.

Lemma3.3.2ConsidertheinputsequencewhereallverticesinIh−1arrivefirstinanyorder,followedbyallverticesinIh−2alsoarrivinginanarbitraryorder.Thiscontinuesuntilthesinglenode(theroot)inI0arrives.FinallyallleavesinIharriveinanyorder.ThentheresultinginputsequencewillcausethealgorithmtouseB(n,t)labelstorankTt.

WewillcalltheinputsequencedefinedinLemma3theworstcaseinputsequence,Wofthealgorithm.Thefollowinglemmaisimmediate.

Lemma3.3.3FortheinputsequenceW,thealgorithmwillassignrankh−itoallverticesinIi,fori=h−1,h−2,...,0,andtheleavesinIhwillbeassignedranksh+1,h+2,...,h+th,wherehistheheightofTt.

Whent→∞,Ttconvergestoastar,andB(n,t)→n.SotherankboundB(n,t)remainsvalidforastar.

Chapter4

On-LineVertex-RankingofSimpleGraphs

Inthischapterwedescribeanon-linealgorithmforrankingtheverticesofasimplegraph.In4.1wedelineatethemainideaofthealgorithmandpresentthepseudo-codeofthealgorithm.Thealgorithmisbasedontheconceptofvisiblevertexandvisibilitylistwhichareexplainedinchapter2.Weendthischapterbyprovingthecorrectnessandderivingthetimecomplexityofthealgorithminsection4.2.

4.1TheAlgorithm

InthissectionweprovethattheverticesofasimplegraphGcanberankedinO(n·m)time,wherenandmarethenumbersofverticesandedgesinG,respectively.WedefineablockingfunctionψfromV(G)to{0,1}asfollows

ψ:V(G)→{0,1}.

Avertexuwillbeblocked,thatis,ψ(u)issetto1whenitistraversedforthefirst

33

CHAPTER4.ON-LINEVERTEX-RANKINGOFSIMPLEGRAPHS34

time.Avertexuwillbefreed,thatis,ϕ(u)issetto0whenthetraversalreturnstotheneighborofufromwhichuwastraversed.Wehavethefollowingtheorem.

Theorem4.1.1TheverticesofasimplegraphGcanberankedusinganon-linealgorithminO(n·m)time,wherenandmarethenumbersofverticesandedgesinG,respectively.

CHAPTER4.ON-LINEVERTEX-RANKINGOFSIMPLEGRAPHS35

recursivedepthfirstsearchtraversalinordertofindalltheranksvisiblefromvi.ForasimplegraphGtherecanbemorethanonepathbetweenanypairofvertices.ToavoidfallingintoinfinitetraversalloopsduetocyclesinG,avertexisblockedwhenitistraversedforthefirsttime.Thevertexisfreedonlywhentherecursivesearchforallneighbors(excepttheneighborfromwhichthevertexwastraversed)havereturned.ThetechniquesofbuildingthevisibilitylistL(vi)andusingL(vi)tofindtherankofviaresimilartoAlgorithm1.However,therankϕ(u)ofavertexumaybevisiblefromvithroughmorethanonepathfromvitou.Inthatcaseϕ(u)isaddedonlyoncetoL(vi).Todothis,theverticesv1,...,vi−1aremarkedaswhiteatthebeginningoftheithiteration.Whenwefindavisiblevertexu,wecheckwhetheruismarkedaswhite.Ifuismarkedaswhite,weaddϕ(u)toL(vi)andmarkuasblack.Thepseudo-codeofthealgorithmisgivenbelow.Algorithm2Online

Simple

CHAPTER4.ON-LINEVERTEX-RANKINGOFSIMPLEGRAPHS

4:5:6:

36

endforψ(v):=0;

findminimumαsuchthatα∈/Landcount(L,β)≤1,foreachβsatisfyingα+1≤β≤max{L};

7:

ϕ(v):=α;󰀵rankvwithα

ProcedureBuildVisibleListGraph(v,u,rmax)

1:2:3:4:5:6:7:8:9:10:11:12:13:14:

ψ(u):=1;

ifuisawhitevertexandϕ(u)>rmaxthenL:=L∪{ϕ(u)};markuasblackvertex;endif

letN(u)bethesetofneighborsofuinC(vi);if(N(u)\\{v})=∅thenforeachw∈(N(u)\\{v})doifψ(w)=0then

BuildVisibleListGraph(u,w,max{rmax,ϕ(u)});endifendforendifψ(u):=0;

4.2CorrectnessProofandComplexityAnalysis

InthissectionweprovethecorrectnessofAlgorithm2.Wealsoderivethetime-complexityofthealgorithm.

CHAPTER4.ON-LINEVERTEX-RANKINGOFSIMPLEGRAPHS37

Wheni=1,thatis,whenthefirstvertexv1arrives,itdoesnothaveanycurrentneighbor,andsoitcanbetriviallyrankedwith1withoutviolatingthevertex-rankingproperty.Wheni>1,weinductivelyassumethattheverticesv1,...,vi−1havebeenproperlyrankedinthepreviousi−1iterations.Wenowprovethatviisproperlyrankedattheithiteration.Atfirstweshowthatthevisibilitylistiscorrectlyconstructedattheithiterationofthealgorithm.Wehavethefollowinglemma.

Lemma4.2.1Letvi∈V(G)bethenewlyarrivedvertexattheithiteration,andletLbethelistconstructedbyAlgorithm2forthevertexvi.ThenL=L(vi),thatis,(i)Lcontainsalltheranksvisiblefromviunderϕ;and(ii)Ldoesnotcontainanyrankinvisiblefromviunderϕ.Proof.

(i)Foracontradiction,assumethatγisarankvisiblefromviunderϕbut

γ∈/L.Letubeavisiblevertexwithrankϕ(u)=γ.ConsiderapathP∈P(vi,u)andletwbetheneighborofvionP.Sinceγisvisiblefromvi,alltheverticesfromwtouhaveranks≤γ.Sinceϕisavertex-ranking,wehaveϕ(v)<γforallinternalverticesvonP.ThusthelargestrankseensofarfromwtotheneighborofuonPis<γ.SowhenuwillbetraversedalongP,wehaveϕ(u)=γ>rmax.SoγmustbeaddedtoL.Thiscontradictsγ∈/L.ThusLcontainsalltheranksvisiblefromvi.

(ii)Foracontradiction,assumethatLcontainsarankγthatisinvisiblefromviunderϕ.Letubeavertexwithϕ(u)=γ.ConsidersomepathP∈P(vi,u)andletwbetheneighborofvionP.Sinceγisinvisiblefromvi,theremustbeavertexzonPinbetweenviandusuchthatϕ(z)>γ.AtanyvertexonPtraversedafterz,wehavermax≥ϕ(z).SinceuistraversedafterzonP,atu,wehavermax≥ϕ(z)andϕ(z)>γ.Thereforeatu,wehavermax>ϕ(u).Soϕ(u)=γcannotbeaddedtoL.SoLcannotcontainanyinvisiblerank.

2

CHAPTER4.ON-LINEVERTEX-RANKINGOFSIMPLEGRAPHS38

Nextweshowthattherankchosenforvi,thecurrentnewvertex,doesnotviolatethevertex-rankingpropertyinC(vi).

Lemma4.2.2Therankαproperlyranksthenewlyarrivedvertexvi∈V(G)attheithiteration.

Proof.Foracontradiction,assumethatαdoesnotproperlyrankvi.SoC(vi)will

containapathP∈P(x,y)forsomex,y∈C(vi)suchthatvi∈V(P),ϕ(x)=ϕ(y)=γ,andϕ(v)≤γforallverticesv∈V(P).Thenϕ(vi)=α≤γandbothϕ(x)andϕ(y)arevisiblefromviunderϕ.Socount(L(vi),γ)≥2.Asα∈/L(vi),α=γisnotpossible.Thusγ≥α+1.ButaccordingtotheAlgorithm2,count(L(vi),β)≤1,foreachβsatisfyingα+1≤β≤max{L(vi)}.Soαproperlyranksvi.

2

ProofofTheorem4.1.1:TheprocedureBuildVisibleListGraphiscalledexactlyonceforeachvertexv∈V(C(vi))\\{vi}foreachexecutionofRankGraph.DuringanexecutionofBuildVisibleListGraph,thelooponLines7-11isexecutedatmostd(v)times.󰀂

SothetotalcostofalltheBuildVisibleListGraphprocedurecallsisd(v)=O(ec),whereecisthenumberofedgesinC(vi).SinceC(vi)is

v∈V(C(vi))\\{vi}

connected,itmusthaveatleastnc−1edges,wherencisthenumberofverticesinC(vi).Soec≥nc−1.Thennc≤ec+1.SincethesizeofthevisibilitylistisO(nc)=O(ec),searchinginL(vi)tofindtherankαinLine6ofprocedureRankGraphtakesO(ec)time.

SowecansaythattheRankGraphproceduretakestimeO(ec)=O(m).

SincetheprocedureRankGraphiscalledforeachnewlyarrivedvertex,andthenverticesv1,...,vnarriveoneatatime,thetotaltimecomplexityofAlgorithm2is󰀂

2v∈V(G)O(m)=O(n)·O(m)=O(n·m).

Chapter5

On-LineEdge-RankingofTrees

Inthischapterweshalldescribeanon-linealgorithmforrankingtheedgesofatreeTinO(n2)time,wherenisthenumberofverticesinT.In5.1wedelineatethemainideaofthealgorithmandpresentthepseudo-codeofthealgorithm.Thealgorithmisbasedontheconceptofvisibleedgeandvisibilitylistwhichareexplainedinchapter2.Weendthischapterbyprovingthecorrectnessandderivingthetimecomplexityofthealgorithminsection5.2.

5.1TheAlgorithm

Inthissectionwedescribethemainideaofthealgorithmandpresentthepseudo-code.Wehavethefollowingtheorem.

Theorem5.1.1TheedgesofatreeTcanberankedusinganon-linealgorithminO(n2)time,wherenisthenumberofverticesinT.

39

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES40

Figure5.2showsanoptimaledge-rankingofthetreeinfigure5.1,whereasfigure5.3depictsanedge-rankingofthesametreeproducedbyouron-linealgorithmforthesequencee5,e8,e4,e11,e1,e13,e2,e10,e9,e14,e6,e3,e12,e7.

e9e8e1e2e3e4e5e7e6e11e12e13e14e10Figure5.1:AtreeT󰀇.

12313214154312Figure5.2:(a)Anoptimaledge-rankingofthetreeinfigure5.1.

IntheremainderofthissectionweproveTheorem5.1.1bygivinganon-linealgorithmforrankingtheedgesofatreeTintimeO(n2).Itisbasedonthegreedyfirst-fitcoloringheuristic.Attheithiteration,thealgorithmtakesasinputthenewly

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES41

321132211352Figureby

the

5.3:(b)Anedge-rankingofthefor

treethe

infigure5.1producedsequence

proposedon-linealgorithmedgearrival

e5,e8,e4,e11,e1,e13,e2,e10,e9,e14,e6,e3,e12,e7.

arrivededgeei.Wethenrankeiwiththeleastpossiblerankwithoutviolatingtheedge-rankingproperty.Torankei,weconstructthevisibilitylistL(ei)bysearchinginT(ei)tofindallvisibleranks.Thesearchiscarriedoutbyarecursivedepthfirstsearchtraversal.Duringthesearch,wekeeptrackofthelargestrankofanedgeonapathstartingfromendpointsofeiseensofar.Asthetraversalcontinuesalongapath,ifanedgeistraversedthathasarankgreaterthanthecurrentmaximum,thenthatrankisaddedtoL(ei)andthelargestrankisupdated.Sinceanyedgeadjacenttoeiistriviallyvisiblefromanendpointofeiunderϕ,itsrankmustbelongtoL(ei).Toincorporatethiscaseintothealgorithm,thelargestrankissetto0atthebeginningofthesearch.Asaresultwhenanedgeeadjacenteiistraversed,itsrankϕ(e)willbetriviallygreaterthan0andaddedtoL(ei).Thepseudo-codeofthealgorithmisgivenbelow.

Algorithm3On

Edge

Tree

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES

1:2:3:4:5:6:

42

fori=1tomdoreadanewedgeei;

letE󰀇={e󰀇1,e󰀇2,...,e󰀇p}bethesetofedgesadjacenttoeiin{e1,e2,...,ei−1};L:=∅;

RankEdge(ei,E󰀇);endfor

󰀵CurrentlyListhevisibilitylistofei,thatisL=L(ei)

ProcedureRankEdge(e,E󰀇)

1:2:3:4:

forj=1topdo

󰀵p=|E󰀇|

BuildVisibleListETree(e,e󰀇j,0);endfor

findminimumαsuchthatα∈/Landcount(L,β)≤1,foreachβsatisfyingα+1≤β≤max{L};

5:

ϕ(e):=α;󰀵rankewithα

ProcedureBuildVisibleListETree(e,e󰀇,rmax)

1:2:3:4:5:6:7:8:9:

ifϕ(e󰀇)>rmaxthenL:=L∪{ϕ(e󰀇)};endif

letE(e󰀇)bethesetofedgesadjacenttoe󰀇inT(ei);if(E(e󰀇)\\{e})=∅then

foreachedgee󰀇󰀇∈(E(e󰀇)\\{e})do

BuildVisibleListETree(e󰀇,e󰀇󰀇,max{rmax,ϕ(e󰀇)});endforendif

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES43

5.2CorrectnessProofandComplexityAnalysis

Inthissectionweprovethecorrectnessofthealgorithmandanalyzeitsrun-time.Wheni=1,thatis,whenthefirstedgee1arrives,itdoesnothaveanyadjacentedges,andsoitcanbetriviallyrankedwith1withoutviolatingtheedge-rankingproperty.Wheni>1,weinductivelyassumethattheedgese1,...,ei−1havebeenproperlyrankedinthepreviousi−1iterations.Wenowprovethateiisproperlyrankedattheithiteration.Atfirstweshowthatthevisibilitylistiscorrectlyconstructedattheithiterationofthealgorithm.Wehavethefollowinglemma.

Lemma5.2.1Letei∈E(T)bethenewlyarrivededgeattheithiteration,andletLbethelistconstructedbyAlgorithm3fortheedgeei.ThenL=L(ei),thatis,(i)Lcontainsalltheranksvisiblefromanendpointofeiunderϕ;and(ii)Ldoesnotcontainanyrankinvisiblefrombothendpointsofeiunderϕ.Proof.

(i)Foracontradiction,assumethatγisarankvisiblefromanendpoint

vofeiunderϕbutγ∈/L.Letebeavisibleedgewithrankϕ(e)=γ,wheree∈E(T(ei))\\{ei}.Sinceγisvisiblefromtheendpointvofei,alltheedgesonP(v,e)haveranks≤γ.Lete󰀇betheedgeincidenttovonP(v,e)ande󰀇󰀇betheedgeadjacenttoeonP(v,e).Sinceϕisavertex-ranking,wehaveϕ(e󰀇󰀇󰀇)<γforalledgese󰀇󰀇󰀇∈E(P(e󰀇,e󰀇󰀇)).Thusthelargestrankseensofarfrome󰀇toe󰀇󰀇onP(v,e)is<γ.SowhenewillbetraversedonP(v,e),wehaveϕ(e)=γ>rmax.SoγmustbeaddedtoL.Thiscontradictsγ∈/L.ThusLcontainsalltheranksvisiblefromanendpointofei.

(ii)Foracontradiction,assumethatLcontainsarankγthatisinvisiblefrombothendpointsuandvofeiunderϕ.Letebeavertexwithϕ(e)=γ.Lete󰀇betheedge

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES44

incidenttovonP(v,e).Sinceγisinvisiblefromtheendpointvofei,theremustbeanedgee󰀇󰀇∈E(P(v,e))\\{e}suchthatϕ(e󰀇󰀇)>γ.AtanyedgeonP(v,e)traversedaftere󰀇󰀇,wehavermax≥ϕ(e󰀇󰀇).Sinceeistraversedaftere󰀇󰀇onP(v,e),ate,wehavermax≥ϕ(e󰀇󰀇)andϕ(e󰀇󰀇)>γ.Thereforeate,wehavermax>ϕ(e).Soϕ(e)=γcannotbeaddedtoL.SoLcannotcontainanyinvisiblerank.

2

Nextweshowthattherankchosenforei,thecurrentnewedge,doesnotviolatetheedge-rankingpropertyinT(ei).

Lemma5.2.2Therankαproperlyranksthenewlyarrivededgeei∈E(T)attheithiteration.

Proof.Foracontradiction,assumethatαdoesnotproperlyrankei.SoT(ei)

willcontainapathP(e󰀇,e󰀇󰀇)forsomee󰀇,e󰀇󰀇∈E(T(ei))suchthatei∈E(P(e󰀇,e󰀇󰀇)),ϕ(e󰀇)=ϕ(e󰀇󰀇)=γ,andϕ(e)≤γforalledgese∈E(P(e󰀇,e󰀇󰀇)).Letei=(u,v).Thenϕ(ei)=α≤γandϕ(e󰀇)isvisiblefromuandϕ(e󰀇󰀇)isvisiblefromvunderϕ.Socount(L(ei),γ)≥2.SincebyAlgorithm3α∈/L(ei),α=γisnotpossible.Thusγ≥α+1.ButaccordingtoAlgorithm3,count(L(ei),β)≤1,foreachβsatisfyingα+1≤β≤max{L(ei)}.Soαproperlyranksei.

2

ProofofTheorem5.1.1:ForeachexecutionoftheRankEdgeprocedure,thevisibilitylistisconstructedbytheBuildVisibleListETreeprocedureusingarecursivedepthfirstsearch(DFS)traversal.Foratree,thecomplexityofDFSisO(|E|)=O(|V|)=O(n),soittakesO(n)timetobuildthevisibilitylist.SincethesizeofthevisibilitylistisO(|E(T(ei))|)=O(|E|)=O(|V|)=O(n),searchinginL(ei)tofindtherankαinLine4ofprocedureRankEdgetakesO(n)time.SowecansaythattheRankEdgeproceduretakestimeO(n).SincetheprocedureRankEdgeiscalledfor

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES45

eachnewlyarrivededge,andthemedgese1,e2...,emarriveoneatatime,thetotal

󰀂m

timecomplexityofAlgorithm3isi=1O(n)=O(m)·O(n)=O(n)·O(n)=O(n2),sinceforatreem=n−1.

2

5.3On-LineEdge-RankingofTreeswithBatchArrivalofEdges

Inthissectionwedefineaslightvariantoftheon-lineedge-rankingmodelcalledon-lineedge-rankingwithbatcharrivalofedges.Inthismodel,theverticesv1,v2...,vnarriveoneatatimeinanyorder.Whenthevertexviarrivesintheithiteration,theedgesfromvitoitsneighborsamongv1,v2...,vi−1arerankedonebyone.Thatis,morethanoneedgeisrankedineachiteration.Weshallgiveanalgorithmforon-lineedge-rankingoftreesinthismodel,proveitscorrectnessandshowthatithasthesametime-complexityastheon-lineedge-rankingalgorithmintheoriginalmodel.

5.3.1Preliminaries

LetT=(V,E)beatree.Foralledgesex,ey∈V(T),wedenotetheuniquepathfromextoeybyP(ex,ey).Foranyu,v∈V(T),wedenotethenumberofedgesonthepathfromutovbydp(u,v).

Letvibethenewlyarrivedvertexattheithiterationofanon-linealgorithm.Wedenotethesetofneighborsofviamong{v1,v2,...,vi−1}byN∗(vi).LetN∗(vi)={u1,u2,...,um}andE∗(vi)={e(vi,uj)|j∈{1,2,...,m}},wherem=|N∗(vi)|.Intheon-lineedge-rankingmodel,eachedgeinE∗(vi)arriveatthesametimeandtheyarerankedonebyone.Sinceujisthejthneighborofvi,e(vi,uj)isthejthedge

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES46

toberankedintheithiteration.Thentheedgese(vi,u1),e(vi,u2),...,e(vi,uj−1)havealreadybeenrankedandedgese(vi,uj+1),e(vi,uj+2),...,e(vi,um)havenotbeenrankedyet.LetVs={x∈{v1,v2,...,vi−1}|suchthatxisconnectedtous},for

󰀁

s∈{1,2,...,m}andT(vi)=T[(jt=1Vt)∪{vi}].Letϕbeanedge-labelingofagraphGwithpositiveintegers.Wedenotetherank(label)ofanedgeebyϕ(e).Consideranyedgeev∈E(T(vi))\\{eij}.Thedefinitionofavisiblerankconsistsoftwocases:

•Thepathfromvitoevcontainseij:Inthiscase,letwjbetheneighborofujonPandwj=vi.Thentherankϕ(ev)ofevissaidtobevisiblefromviunderϕifalltheedgesfrome(uj,wj)toevonPhaveranks≤ϕ(ev).

•Thepathfromvitoevdoesnotcontaineij:Inthiscase,letejbetheedgeonPincidenttovi.Thentherankϕ(ev)ofevisvisiblefromviunderϕifalledgesfromejtoevonPhaveranks≤ϕ(ev).

Suchanedgeevisthencalledavisibleedge.Whilerankingeij,thelistofallranksvisiblefromviunderϕiscalledthevisibilitylistofeij,andisdenotedbyL(eij).L(eij)willingeneralbeamulti-set,whereanelementγinL(eij)canappearmorethanonce.Arankthatisnotvisiblefromviunderϕiscalledaninvisiblerank.Foranyintegerγwedenotebycount(L(eij),γ)thenumberofγ’scontainedinL(eij).WedenotethelargestrankinL(eij)bymax{L(eij)}.IfL(eij)=∅,thenweassumethatmax{L(eij)}=0.

5.3.2TheAlgorithm

Wenowdiscussthemainideaofthealgorithmandpresentthepseudo-codeofthealgorithm.Wehavethefollowingtheorem.

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES47

Theorem5.3.1TheedgesofatreeTcanberankedusinganon-linealgorithminO(n2)time,wherenisthenumberofverticesinTandtheedgesarriveinbatches.

Intheremainderofthissectionwegiveanon-linealgorithmforrankingtheedgesofatreeTintimeO(n2).Itisbasedonthegreedyfirst-fitcoloringheuristic.Ateachiteration,theedgesfromthenewlyarrivedvertextoitsneighborsamongthepreviouslyarrivedverticesareranked(colored)withtheleastpossiblerank(color)withoutviolatingtheedge-rankingproperty.Attheithiteration,thealgorithmtakesasinputthenewlyarrivedvertexviandalistofitsneighborsin{v1,...,vi−1}.WethenrankeachedgeinE∗(vi)withtheleastpossibleranks.Whenweranke(vi,ej),forj∈{1,2,...,m},edgese(vi,ej+1),e(vi,ej+2),...,e(vi,em)havenotbeenranked

󰀁

yet,andtheranksofedgesinT[(mt=j+1Vt)]willnotaffecttheranktobechosenfore(vi,uj).Forconvenience,lete(vi,uj)=eij.Torankeij,weconstructthevisibilitylistL(eij)bysearchinginT(vi)tofindallvisibleranks.Thesearchiscarriedoutbyarecursivedepthfirstsearchtraversal.Duringthesearch,wekeeptrackofthelargestrankofanedgeonapathstartingfromviseensofar.Asthetraversalcontinuesalongapath,ifanedgeistraversedthathasarankgreaterthanthecurrentmaximum,thenthatrankisaddedtoL(eij)andthelargestrankisupdated.Sinceanyedgeadjacenttoeijistriviallyvisiblefromviunderϕ,itsrankmustbelongtoL(vi).Toincorporatethiscaseintothealgorithm,thelargestrankissetto0atthebeginningofthesearch.Asaresultwhenanedgeeadjacenteijistraversed,itsrankϕ(e)willbetriviallygreaterthan0andaddedtoL(eij).Thepseudo-codeofthealgorithmisgivenbelow.Algorithm4On

Edge

Tree

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES

3:4:5:6:7:8:9:10:11:

48

letmbethenumberofneighborsofviin{v1,v2,...,vi−1};forj=1tomdo

selectuj,thejthneighborofvi;leteijbetheedgebetweenvianduj;letUj={u1,u2,...,uj−1};L:=∅;

󰀵CurrentlyListhevisibilitylistofeij,thatisL=L(eij)

RankEdgeBatch(vi,eij,uj,j,Uj);endforendfor

ProcedureRankEdgeBatch(v,e,u,j,U)

1:2:3:4:5:6:7:8:9:10:11:12:

letN(u)={w1,w2,...,wp}bethesetofcurrentneighborsofuexceptv;ifN(u)=∅then

letekbetheedgebetweenuandwkforallk∈{1,2,...,p};endif

fork=1topdo

BuildVisibleListBatch(e,u,ek,wk,0);endfor

foreachx∈Udo

letexbetheedgebetweenvandx;BuildVisibleListBatch(e,v,ex,x,0);endfor

findminimumαsuchthatα∈/Landcount(L,β)≤1,foreachβsatisfyingα+1≤β≤max{L};

13:

ϕ(e):=α;󰀵rankewithα

CHAPTER5.ON-LINEEDGE-RANKINGOFTREESProcedureBuildVisibleListBatch(e1,u1,e2,u2,rmax)

1:2:3:4:5:6:7:8:9:10:

49

ifϕ(e2)>rmaxthenL:=L∪{ϕ(e2)};endif

letN(u2)={x1,x2,...,xq}bethesetofcurrentneighborsofu2exceptu1;ifN(u2)=∅thenforl=1toqdo

letelbetheedgebetweenu2andxl;

BuildVisibleListBatch(e2,u2,el,xl,max{rmax,ϕ(e2)});endforendif

5.3.3CorrectnessProofandComplexityAnalysis

Inthissectionweprovethecorrectnessofthealgorithmandanalyzeitsrun-time.Wheni=1,thatis,whenthefirstvertexv1arrives,itdoesnothaveanycurrentneighbor,andsotherearenoedgestoberanked.Wheni>1,weassumethattheedgesthatarrivedinthepreviousi−1iterationsandedgese(vi,e1),e(vi,e2),...,e(vi,ej−1)havebeencorrectlyranked.

Firstweprovethatthevisibilitylistiscorrectly

constructedfore(vi,uj)=eijattheithiterationofthealgorithm.Wehavethefollowinglemma.

Lemma5.3.2Letvi∈V(T)bethenewlyarrivedvertexattheithiterationandujbethejthneighborofvi.LeteijbetheedgebetweenviandujandLbethelistconstructedbyAlgorithm4fortheedgeeij.ThenL=L(vi),thatis,(i)Lcontainsalltheranksvisiblefromviunderϕ;and

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES(ii)Ldoesnotcontainanyrankinvisiblefromviunderϕ.

50

Proof.(i)Foracontradiction,assumethatγisarankvisiblefromviunderϕbut

γ∈/L.Letevbeavisibleedgewithrankϕ(ev)=γ.LetPbetheuniquepathfromvitoev.Assumethattheendpointsofevarexandyanddp(vi,x)=dp(vi,y)−1.LetukbetheneighborofvionpathP,wherek∈{1,2,...,j}.LetzbetheneighborofxonPandz=y.Wehavethefollowingtwocases:

•k=j:Inthiscase,letwjbetheneighborofujonPandwj=vi.Sinceevisvisible,alledgesfrome(uj,wj)toe(z,x)haveranks≤γ.Sinceϕisenedge-ranking,thenalledgesfrome(uj,wj)toe(z,x)haveranks<γ.

•k∈{1,2,...,j−1}:Inthiscase,sinceevisvisible,alledgesfromevi,ujtoe(z,x)haveranks≤γ.Becauseϕisanedge-ranking,alledgesfrome(vi,uj)toe(z,x)haveranks<γ.

Sothelargestrankseenuntilevistraversedis<γ.Sowhenevistraversed,wehaveϕ(ev)=γ>rmax.SoγmustbeaddedtoL.Thiscontradictsγ∈/L.ThusLcontainsalltheranksvisiblefromviunderϕ.

(ii)Foracontradiction,assumethatLcontainsarankγthatisinvisiblefromviunderϕ.Letevbeanedgewithϕ(ev)=γ.ConsidertheuniquepathPfromvitoev.Wehavethefollowingtwocases:

•eij∈E(P):Inthiscase,lete1betheedgeadjacenttoevonP.Sinceevisinvisiblefromvi,theremustbeanedgee2onPbetweene1andevsuchthatϕ(e2)>γ.•eij∈/E(P):Inthiscase,lete1betheedgeincidenttovionP.Sinceevisinvisiblefromvi,theremustbeanedgee2onPbetweene1andevsuchthatϕ(e2)>γ.Inbothcases,aftere2hasbeentraversed,wehavermax>ϕ(e2).Sinceevwill

CHAPTER5.ON-LINEEDGE-RANKINGOFTREES51

betraversedaftere2onP,wehaveatev,rmax≥ϕ(e2)andϕ(e2)>ϕ(ev)=γ.Soϕ(ev)=γcannotbeaddedtoL.SoLcannotcontainanyinvisiblerank.

2

Lemma5.3.3Attheithiteration,therankαproperlyrankstheedgeeijbetweenthenewlyarrivedvertexvianduj,thejthselectedneighborofvi.

Proof.Foracontradiction,assumeαdoesnotproperlyrankeij.SoT(vi)will

containapathP(e1,e2)forsomee1,e2∈E(T(vi))suchthateij∈E(P(e1,e2))andϕ(e1)=ϕ(e2)=γandϕ(e)≤γforalledgese∈E(P(e1,e2)).Thenϕ(eij)=α≤γandbothϕ(e1)andϕ(e2)arevisiblefromviunderϕ.Socount(L(eij),γ)≥2.Asα∈/L(eij),α=γisnotpossible.Soγ≥α+1.butaccordingtoAlgorithm4,count(L(eij),β)≤1forallβsatisfyingα+1≤β≤max{L}.Soαproperlyrankseij.

2

ProofofTheorem5.3.1:TheprocedureBuildVisibleListBatchiscalledexactlyonceforeachvertexv∈V(T(vi))\\{vi}foreachexecutionofRankEdgeBatch.DuringanexecutionofBuildVisibleListBatch,theloopsonLines5-7andLines8-11isexecutedatmostd(v)times.SothetotalcostofalltheBuildVisibleListBatchprocedurecalls󰀂isv∈V(T(vi))\\{vi}d(v)=O(et)=O(m)=O(n),whereetisthenumberofedgesinT(vi).SincethesizeofthevisibilitylistisO(|V(T(vi))|)=O(n),searchinginL(vi)tofindtherankαinLine12ofprocedureRankEdgeBatchtakesO(n)time.SowecansaythattheRankEdgeBatchproceduretakestimeO(n).Sothetotaltime

󰀂󰀂d(vi)󰀂n󰀂n

complexityofAlgorithm4isnO(n)=O(n)·d(v)=O(n)ii=1j=1i=1i=1d(vi)=O(n)·O(m)=O(n)·O(n)=O(n2).

2

Chapter6

ConclusionsandOpenProblems

Thisthesisdealswithon-linevertex-rankingandon-lineedge-rankingproblems.Wenewlydefinetheon-lineedge-rankingmodelandarelaxationoftheon-lineedge-rankingmodel,wheremorethanoneedgearrivesateachiteration.Therelaxedon-lineedge-rankingmodelistermedon-lineedge-rankingwithbatcharrivalofedges.Wethenprovidepolynomial-timeon-linealgorithmsforedge-rankingoftreesinbothmodels.Efficienton-linealgorithmsforvertex-rankingofsimplegraphsandtreesarealsopresentedinthisthesis.

Wenowrecapthekeycontributionsofthedissertationanddiscussdirectionsforfutureresearch.Chapter1givesanelaborateliteraturereviewofthevertex-rankingandedge-rankingproblems.

Inchapter2weprovidesomemathematical,graph-

theoreticandalgorithmicdefinitionsandconceptsthathavebeenusedthroughoutthisthesis.Inchapter3weprovideanon-linevertex-rankingalgorithmfortreeswhichrunsinO(n2)time,whichisanimprovementoverthepreviouslybestknownalgorithmwhichrequiredO(n3)time[21].Upperboundsonthenumberofranksusedbythealgorithmfortwospecialsub-classesoftrees,namelystarsandcompletet-arytrees

52

CHAPTER6.CONCLUSIONSANDOPENPROBLEMS53

arederivedinthischapter.Chapter4givesforthefirsttimeanon-linealgorithmforthevertex-rankingofasimplegraphinO(n·m)time.Inchapter5wenewlydefinetheon-lineedge-rankingmodelinwhichtheedgesoftheinputgrapharriveoneatatimeineachiteration.Wethengiveanon-lineedge-rankingalgorithmfortreesinthismodelwhichrunsinO(n2)time.Thebatcharrivaledge-rankingmodelisdefinedinthischapterwheremorethanoneedgearrivesineachiterationandwegiveaquadratic-timeon-linealgorithmforrankingtheedgesofatreeinthismodel.Wehopebothoftheseon-lineedge-rankingmodelswillhaveimportantpracticalapplicationsinrealworldproblemssuchas,VLSIlayout,parallelassemblyofproductsetc.Allofthechapterscontainrelevantdefinitions,conceptsandcorrectnessproofsofthealgorithms.Inthisthesiswehaveprovidedefficientpolynomialtimeon-linealgorithmsforvertex-rankingandedge-rankingproblems.Howevermuchremainstodointhisareaandweidentifythefollowingproblemsonwhichwewishtoworkoninthefuture.

1.Findrankboundsfortheon-linealgorithmsprovidedinthisthesis.Unlessthisisdone,itisnotpossibletofindtheperformanceratioofouron-linealgorithmsagainstanoptimaloff-linealgorithm.

2.Developlinear-timeon-linealgorithmsforvertex-rankingandedge-rankingoftrees.

3.Investigatewhetherthereareanyon-linerankingstrategiesotherthanthegreedystrategywhichmightgivebetterresultsregardingtherankbound.

4.Delineatespecificpracticalapplicationareasfortheon-lineedge-rankingproblem.

Bibliography

[1]A.V.Aho,J.E.Hopcroft,andJ.D.Ullman,TheDesignandAnalysisofComputer

Algorithms,Addison-Wesley,Reading,MA,1974.

[2]H.L.Bodlaender,J.S.Deogun,K.Jansen,T.Kloks.D.Kratsch,H.M¨uller,

andZs.Tuza,Rankingsofgraphs,SocietyforIndustrialandAppliedMathematics(SIAM)JournalonDiscreteMathematics.21(1998),pp.168-181.

[3]H.L.Bodlaender,J.R.Gilbert,H.Hafsteinsson,andT.Kloks,Approximating

treewidth,pathwidthandminimumeliminationtreeheight,JournalofAlgorithms,18(1995),pp.238-255.

[4]E.Bruoth,andM.Horˇna´k,On-linerankingnumberforcyclesandpaths,

DiscussionesMathematicae,GraphTheory19(1999),pp.175-197.

[5]J.S.Deogun,T.Kloks,D.Kratsch,andH.M¨uller,Onvertexrankingfor

permutationandothergraphs,Proceedingsofthe11thAnnualSymposiumonTheoreticalAspectsofComputerScience,LectureNotesinComputerScience,Springer-Verlag,775(1994),pp.747-758.

[6]J.S.Deogun,andY.Peng,Edgerankingoftrees,CongressusNumerantium,79

(1990),pp.19-28.

54

BIBLIOGRAPHY55

[7]I.S.Duff,andJ.K.Reid,Themultifrontalsolutionofindefinitesparsesymmetric

linearequations,AssociationforComputingMachinery(ACM)TransactionsonMathematicalsoftware,9(1983),pp.302-325.

[8]M.R.GareyandD.S.Johnson,ComputersandIntractability:AGuidetothe

TheoryofNP-Completeness,W.H.FreemanandCompany,NewYork,Reprintofthe1979original,2000.

[9]A.V.Iyer,H.D.Ratliff,andG.Vijayan,Onanedge-rankingproblemoftreesand

graphs,DiscreteAppliedMathematics,30(1991),pp.43-52.

[10]A.V.Iyer,H.D.Ratliff,andG.Vijayan,Optimalnoderankingoftrees,

InformationProcessingLetters,28(1988),pp.225-229.

[11]A.V.Iyer,H.D.Ratliff,andG.Vijayan,Parallelassemblyofmodularproducts

-ananalysis,TechnicalReportPlanningandDesignResourceCenter,TechnicalReport88-06,GeorgiaInstituteofTechnology,1988.

[12]M.A.Kashem,andM.Z.Rahman,Anoptimalparallelalgorithmforc-vertex-rankingoftrees,InformationProcessingLetters,92(2004)pp.179-184alsoinProceedingsofthe14thInternationalSymposiumonAlgorithmsandComputation(ISAAC’03),LectureNotesinComputerScience,Springer-Verlag,2906(2003)pp.4-473.

[13]M.A.Kashem,andM.E.Haque,Edge-rankingproblemisNP-completeforseries-parallelgraphs,Proceedingsofthe4thInternationalConferenceonComputerandInformationTechnology(ICCIT),2001,pp.108-112.

[14]M.A.Kashem,X.Zhou,andT.Nishizeki,Algorithmsforgeneralizedvertex-rankingsofpartialk-trees,TheoreticalComputerScience,240(2000),pp.407-420.

BIBLIOGRAPHY56

[15]M.A.Kashem,X.Zhou,andT.Nishizeki,Algorithmsforgeneralizededge-rankingsofpartialk-treeswithboundedmaximumdegree,Proceedingsofthe1stInternationalConferenceonComputerandInformationTechnology(ICCIT),1998,pp.45-51.

[16]M.A.Kashem,X.Zhou,andT.Nishizeki,Optimalc-vertex-rankingsofseries-parallelgraphs,Manuscriptinpreparation.

[17]M.Katchalski,W.McCuaig,andS.Seager,Orderedcolourings,Discrete

Mathematics,142(1995),pp.141-154.

[18]T.Kloks,H.M¨uller,andC.K.Wong,Vertexrankingofasteroidaltriple-freegraphs,ProceedingsOfthe7thInternationalSymposiumonAlgorithmsandComputation(ISAAC’96),LectureNotesinComputerScience,Springer-Verlag,1178(1996),pp.174-182.

[19]T.W.Lam,andF.L.Yue,Optimaledgerankingoftreesinlineartime,

Algorithmica,30(2001),pp.12-33.

[20]T.W.Lam,andF.L.Yue,Edgerankingofgraphsishard,DiscreteApplied

Mathematics,85(1998),pp.71-86.

[21]C.Lee,andJ.S.Juan,On-linerankingalgorithmsfortrees,Proceedingsof

theInternationalConferenceonFoundationsofComputerScience,MonteCarloResort,LasVegas,USA,(2005),pp.46-51.

[22]C.E.Leiserson,Area-efficientgraphlayoutsforVLSI,Proceedingsofthe21st

AnnualIEEESymposiumonFoundationsofComputerScience,1980,pp.270-281.

BIBLIOGRAPHY57

[23]J.W.H.Liu,Theroleofeliminationtreesinsparsefactorization,Society

forIndustrialandAppliedMathematics(SIAM)JournalofMatrixAnalysisandApplications,11(1990),pp.134-172.

[24]N.Megiddo,Applyingparallelcomputationalgorithmsinthedesignofserial

algorithms,JournaloftheAssociationforComputingMachinery(ACM),30(1983),pp.852-865.

[25]M.A.H.Newton,andM.A.Kashem,Anefficientalgorithmforoptimalvertex-rankingofpermutationgraphs,Proceedingsofthe2ndInternationalConferenceonComputerandInformationTechnology(ICCIT),1999,pp.315-320.

[26]A.Pothen,Thecomplexityofoptimaleliminationtrees,TechnicalReportCS-88-13,PennsylvaniaStateUniversity,USA,1988.

[27]K.H.Rosen,DiscreteMathematicsandItsApplications,McGraw-Hill,2002.[28]A.A.Sch¨affer,Optimalnoderankingoftreesinlineartime,Information

ProcessingLetters33(19)pp.91-96.

[29]I.Schiermeyer,Zs.Tuza,andM.Voigt,On-linerankingsofgraphs.Discrete

Mathematics,212(2000)pp.141-147.

[30]A.Sen,H.Deng,andS.Guha,Onagraphpartitionproblemwithapplicationto

VLSIlayout,InformationProcessingLetters,43(1992),pp.87-94.

[31]P.delaTorre,R.Greenlaw,andA.A.Sch¨affer,Optimaledgerankingoftreesin

polynomialtime,Algorithmica,13(1995),pp.592-618.

[32]Zs.Tuza,andM.Voigt,Rankingproblemsongraphs,Manuscript,(1995).

BIBLIOGRAPHY58

[33]D.B.West,IntroductiontoGraphTheory,Prentice-Hall,Inc.,NewJersey,

Reprintof1996original,2000.

[34]X.Zhou,M.A.Kashem,andT.Nishizeki,Generalizededge-rankingsoftrees,

TheInstituteofElectronics,InformationandCommunicationEngineers(IEICE)TransactionsonFundamentalsofElectronics,CommunicationsandComputerScience,81-A-2(1998),pp.310-320.

[35]X.Zhou,N.Nagai,andT.Nishizeki,Generalizedvertex-rankingsoftrees,

InformationprocessingLetters,56(1995),pp.321-328.

Index

(V,E),14E(G),14G[V󰀇],15Kn−1,1,19V(G),14∆(G),14NP-hard,21χr(G),5χ󰀇r(G),8δ(G),14c-edge-ranking,9c-edge-rankingnumber,9c-edge-rankingproblem,9c-vertex-ranking,7c-vertex-rankingnumber,7c-vertex-rankingproblem,7d(v),14dG(v),14,23

adjacent,14

algorithm

off-line,22on-line,22ancestor,17

batcharrivalofedges

on-lineedge-ranking,45

child,17cycle,16degree,14depth,18descendant,17edge,14

multipleedge,14edge-coloringproblem,4edge-ranking,7edge-rankingnumber,8edge-rankingproblem,8graph,14

(connected)component,1659

INDEX

connected,16disconnectedgraph,16multigraph,14simplegraph,14heightofarootedtree,18incident,14join,14level,18loop,14neighbors,14node

internal,17leaf,17nodes,17

on-lineranking,10optimalc-edge-ranking,9optimalvertex-ranking,5orderedcoloringproblem,5parent,17path,16

length,16

rank,5

60

rootedtree,17star,19

center,19subgraph,15

inducedbyE󰀇,15inducedbyV󰀇,15tree,17

t-arytree,18binarytree,18completet-arytree,18fullt-arytree,18root,17subtree,18vertex,14

vertex-coloringproblem,3vertex-ranking,5vertex-rankingnumber,5vertex-rankingproblem,5visibilitylistofei,24visibilitylistofvi,23visibleedge,24visiblevertex,23

walk,16

closed,16