You are an expert at summarizing long articles. Proceed to summarize the following text: 
breadth first search ( bfs ) is a fundamental graph traversal strategy . it can also be viewed as computing single source shortest paths on unweighted graphs . it decomposes the input graph @xmath5 of @xmath0 nodes and @xmath6 edges into at most @xmath0 levels where level  @xmath7 comprises all nodes that can be reached from a designated source  @xmath8 via a path of @xmath7  edges , but can not be reached using less than @xmath7 edges . the objective of a dynamic graph algorithm is to efficiently process an online sequence of update and query operations ; see @xcite for overviews of classic and recent results . in our case we consider bfs under a sequence of either @xmath2 edge insertions , but not deletions ( _ incremental _ version ) or @xmath2 edge deletions , but not insertions ( _ decremental _ version ) . after each edge insertion / deletion the updated bfs level decomposition has to be output . we consider the commonly accepted external - memory ( em ) model of aggarwal and vitter @xcite . it assumes a two level memory hierarchy with faster internal memory having a capacity to store @xmath9 vertices / edges . in an i / o operation , one block of data , which can store @xmath10 vertices / edges , is transferred between disk and internal memory . the measure of performance of an algorithm is the number of i / os it performs . the number of i / os needed to read @xmath11 contiguous items from disk is @xmath12 . the number of i / os required to sort @xmath11 items is @xmath13 . for all realistic values of @xmath11 , @xmath10 , and @xmath9 , @xmath14 . there has been a significant number of publications on external - memory graph algorithms ; see  @xcite for recent overviews . however , we are not aware of any dynamic graph algorithm in the fully external - memory case ( where @xmath15 ) . we provide the first non - trivial result on dynamic bfs in external - memory . for general sparse undirected graphs of initially @xmath0 nodes and @xmath1 edges and either @xmath2 edge insertions or @xmath2 edge deletions , we prove an amortized high - probability bound of @xmath3 i / os per update . in contrast , the currently best bound for static bfs on sparse undirected graphs is @xmath16 i / os  @xcite . also note that for general sparse graphs and worst - case monotone sequences of @xmath2 updates in _ internal - memory _ there is asymptotically no better solution than performing @xmath2 runs of the linear - time static bfs algorithm , even if after each update we are just required to report the changes in the bfs tree ( see fig . [ bezug ] for an example ) . in case @xmath4 i / os should prove to be a lower bound for static bfs in external - memory , then our result yields an interesting differentiator between static vs. dynamic bfs in internal and external memory .      in section  [ static ] we will review known bfs algorithms for static undirected graphs . then we consider traditional and new external - memory methods for graph clustering ( section  [ clusters ] ) . subsequently , in section  [ algorithm ] we provide the new algorithm and analyze it in section  [ analysis ] . final remarks concerning extensions and open problems are given in sections  [ extensions ] and  [ conclusions ] , respectively . * internal - memory . * bfs is well - understood in the ram model . there exists a simple linear time algorithm @xcite ( hereafter referred as im_bfs ) for the bfs traversal in a graph . im_bfs keeps a set of appropriate candidate nodes for the next vertex to be visited in a fifo queue @xmath17 . furthermore , in order to find out the unvisited neighbors of a node from its adjacency list , it marks the nodes as either visited or unvisited .    unfortunately , as the storage requirements of the graph starts approaching the size of the internal memory , the running time of this algorithm deviates significantly from the predicted @xmath18 asymptotic performance of the ram model : checking whether edges lead to already visited nodes altogether needs @xmath19 i / os in the worst case ; unstructured indexed access to adjacency lists may add another @xmath20 i / os . + * em - bfs for dense undirected graphs . * the algorithm by munagala and ranade @xcite ( referred as mr_bfs ) ignores the second problem but addresses the first by exploiting the fact that the neighbors of a node in bfs level @xmath21 are all in bfs levels @xmath22 , @xmath21 or @xmath23 . let @xmath24 denote the set of nodes in bfs level @xmath23 , and let @xmath25 be the multi - set of neighbors of nodes in @xmath26 . given @xmath26 and @xmath27 , mr_bfs builds @xmath24 as follows : firstly , @xmath25 is created by @xmath28 random accesses to get hold of the adjacency lists of all nodes in @xmath26 . thereafter , duplicates are removed from @xmath25 to get a sorted set @xmath29 . this is done by sorting @xmath25 according to node indices , followed by a scan and compaction phase . the set @xmath30 is computed by scanning `` in parallel '' the sorted sets of @xmath31 , and @xmath27 to filter out the nodes already present in @xmath26 or @xmath27 . the resulting worst - case i / o - bound is @xmath32 . the algorithm outputs a bfs - level decomposition of the vertices , which can be easily transformed into a bfs tree using @xmath33 i / os @xcite . + * em - bfs for sparse undirected graphs . * mehlhorn and meyer suggested another approach @xcite ( mm_bfs ) which involves a preprocessing phase to restructure the adjacency lists of the graph representation . it groups the vertices of the input graph into disjoint clusters of small diameter in @xmath34 and stores the adjacency lists of the nodes in a cluster contiguously on the disk . thereafter , an appropriately modified version of mr_bfs is run . mm_bfs exploits the fact that whenever the first node of a cluster is visited then the remaining nodes of this cluster will be reached soon after . by spending only one random access ( and possibly , some sequential accesses depending on cluster size ) to load the whole cluster and then keeping the cluster data in some efficiently accessible data structure ( pool ) until it is all processed , on sparse graphs the total amount of i / os can be reduced by a factor of up to @xmath35 : the neighboring nodes of a bfs level can be computed simply by scanning the pool and not the whole graph . though some edges may be scanned more often in the pool , unstructured i / os to fetch adjacency lists is considerably reduced , thereby reducing the total number of i / os . + mehlhorn and meyer @xcite proposed the algorithms mm_bfs_r and mm_bfs_d , out of which the first is randomized and the second is deterministic . in mm_bfs_r , the partitioning is generated `` in parallel rounds '' : after choosing master nodes independently and uniformly at random , in each round , each master node tries to capture all unvisited neighbors of its current sub - graph into its partition , with ties being resolved arbitrarily .    a similar kind of randomized preprocessing is also applied in parallel  @xcite and streaming  @xcite settings . there , however , a dense compressed graph among the master nodes is produced , causing rather high parallel work or large total streaming volume , respectively . the mm_bfs_d variant first builds a spanning tree @xmath36 for the connected component of @xmath34 that contains the source node . arge et al . @xcite show an upper bound of @xmath37 i / os for computing such a spanning tree . each undirected edge of @xmath36 is then replaced by two oppositely directed edges . note that a bi - directed tree always has at least one euler tour . in order to construct the euler tour around this bi - directed tree , each node chooses a cyclic order @xcite of its neighbors . the successor of an incoming edge is defined to be the outgoing edge to the next node in the cyclic order . the tour is then broken at the source node and the elements of the resulting list are then stored in consecutive order using an external memory list - ranking algorithm ; chiang et al . @xcite showed how to do this in sorting complexity . thereafter , we chop the euler tour into _ chunks _ of @xmath38 nodes and remove duplicates such that each node only remains in the first chunk it originally occurs ; again this requires a couple of sorting steps . the adjacency lists are then re - ordered based on the position of their corresponding nodes in the chopped duplicate - free euler tour : all adjacency lists for nodes in the same chunks form a cluster and the distance in @xmath34 between any two vertices whose adjacency - lists belong to the same cluster is bounded by @xmath38 . the preprocessing methods for the static bfs in @xcite may produce very unbalanced clusters : for example , with mm_bfs_d using chunk size @xmath39 there may be @xmath40 clusters being in charge of only @xmath41 adjacency - lists each . for the dynamic version , however , we would like to argue that each random access to a cluster not visited so far provides us with @xmath42 new adjacency - lists . unfortunately , finding such a clustering i / o - efficiently seems to be quite hard . therefore , we shall already be satisfied with an euler tour based randomized construction ensuring that the _ expected _ number of adjacency - lists kept in all but one vertices where @xmath43 denotes the number of vertices in the connected component of the starting node  @xmath8 . ] clusters is @xmath42 . the preprocessing from mm_bfs_d is modified as follows : each vertex  @xmath44 in the spanning tree @xmath36 is assigned an independent binary random number @xmath45 with @xmath46= \mathbf{p}[r(v)=1]=1/2 $ ] . when removing duplicates from the euler tour , instead of storing @xmath44 s adjacency - list in the cluster related to the chunk with the _ first _ occurrence of a vertex  @xmath44 , now we only stick to its first occurrence iff @xmath47 and otherwise ( @xmath48 ) store @xmath44 s adjacency - list in the cluster that corresponds to the _ last _ chunk of the euler tour @xmath44 appears in . for leaf nodes @xmath44 , there is only one occurrence on the tour , hence the value of @xmath45 is irrelevant . obviously , each adjacency - lists is stored only once . furthermore , the modified procedure maintains all good properties of the standard preprocessing within mm_bfs_d like guaranteed bounded distances of @xmath49 in @xmath34 between the vertices belonging to the same cluster and @xmath50 clusters overall .    for chunk size @xmath51 and each but the last chunk , the expected number of adjacency - lists kept is at least @xmath52 . let @xmath53 be the sequence of vertices visited by an arbitrary chunk @xmath54 of the euler tour @xmath55 , excluding the last chunk . let @xmath56 be the number of entries in @xmath57 that represent first or last visits of inner - tree vertices from the spanning tree @xmath36 on @xmath55 . these @xmath56 entries account for an expected number of @xmath58 adjacency - lists actually stored and kept in  @xmath54 . note that if for some vertex @xmath59 both its first and last visit happen within @xmath54 , then @xmath44 s adjacency - list is kept with probability one . similarly , if there are any visits of leaf nodes from @xmath36 within @xmath54 , then their adjacency - lists are kept for sure ; let @xmath60 denote the number of these leaf node entries in @xmath57 . what remains are @xmath61 _ intermediate _ ( neither first nor last ) visits of vertices within @xmath54 ; they do not contribute any additional adjacency - lists . we can bound @xmath61 using the observation that any intermediate visit of a tree node  @xmath44 on @xmath55 is preceded by a last visit of a child @xmath62 of @xmath44 and proceeded by a first visit of another child @xmath63 of @xmath44 . thus , @xmath64 , that is @xmath65 , which implies that the expected number of distinct adjacency - lists being kept for @xmath54 is at least @xmath66 . in this section we concentrate on the incremental version for sparse graphs with @xmath2 updates where each update inserts an edge . thus , bfs levels can only decrease over time . before we start , let us fix some notation : for @xmath67 , @xmath68 is to denote the graph after the @xmath7-th update , @xmath69 is the initial graph . let @xmath70 , @xmath71 , stand for the bfs level of node @xmath44 if it can be reached from the source node  @xmath8 in @xmath72 and @xmath0 otherwise . furthermore , for @xmath73 , let @xmath74 . the main ideas of our approach are as follows :    * checking connectivity ; type a updates . * in order to compute the bfs levels for @xmath72 , @xmath73 , we first run an em connected components algorithm ( for example the one in @xcite taking @xmath75 i / os ) in order to check , whether the insertion of the @xmath7-th edge  @xmath76 enlarges the connected component @xmath77 of the source vertex  @xmath8 . if yes ( let us call this a _ type a update _ ) , then w.l.o.g . let @xmath78 and let @xmath79 be the connected component that comprises  @xmath44 . the new edge @xmath76 is then the only connection between the existing bfs - tree for  @xmath8 and @xmath79 . therefore , we can simply run mr_bfs on the subgraph @xmath80 defined by the vertices in @xmath79 with source  @xmath44 and add @xmath81 to all distances obtained . this takes @xmath82 i / os where @xmath83 denotes the number of vertices in @xmath79 .    if the @xmath7-th update does not merge @xmath77 with some other connected component but adds an edge within @xmath77 ( _ type b update _ ) then we need to do something more fancy :    * dealing with small changes ; type b updates . * now for computing the bfs levels for @xmath72 , @xmath73 , we pre - feed the adjacency - lists into a sorted pool @xmath84 according to the bfs levels of their respective vertices in @xmath85 using a certain advance @xmath86 , i.e. , the adjacency list for @xmath44 is added to @xmath84 when creating bfs level @xmath87 of @xmath72 . this can be done i / o - efficiently as follows . first we extract the adjacency - lists for vertices having bfs levels up to @xmath88 in @xmath85 and put them to @xmath84 where they are kept sorted by node indices . from the remaining adjacency - lists we build a sequence  @xmath89 by sorting them according to bfs levels in @xmath85 ( primary criterion ) and node indices ( secondary criterion ) . for the construction of each new bfs level of @xmath72 we merge a subsequence of @xmath89 accounting for one bfs level in @xmath85 with @xmath84 using simple scanning . therefore , if @xmath90 for all @xmath91 then all adjacency - lists will be added to @xmath84 in time and can be consumed from there without random i / o . each adjacency - list is scanned at most once in @xmath89 and at most @xmath88 times in @xmath84 . thus , if @xmath92 this approach causes less i / o than mm_bfs .    * dealing with larger changes . * unfortunately , in general , there may be vertices  @xmath44 with @xmath93 . their adjacency - lists are not prefetched into @xmath84 early enough and therefore have to be imported into @xmath84 using random i / os to whole clusters just like it is done in mm_bfs . however , we apply the modified clustering procedure described in section  [ ssec : modified : preprocessing ] on @xmath85 , the graph without the @xmath7-th new edge ( whose connectivity is the same as that of @xmath72 ) with chunk size  @xmath94 . note that this may result in @xmath95 cluster accesses , which would be prohibitive for small  @xmath88 . therefore we restrict the number of random cluster accesses to @xmath96 . if the dynamic algorithm does not succeed within these bounds then it increases @xmath88 by a factor of two , computes a new clustering for @xmath85 with larger chunk size and starts a _ new attempt _ by repeating the whole approach with the increased parameters . note that we do not need to recompute the spanning tree for the for the second , third , @xmath97 attempt .    * at most @xmath98 attempts per update . * the @xmath99-th attempt , @xmath100 , of the dynamic approach to produce the new bfs - level decomposition will apply an advance of @xmath101 and recompute the modified clustering for @xmath85 using chunk size @xmath102 . note that there can be at most @xmath103 failing attempts for each edge update since by then our approach allows sufficiently many random accesses to clusters so that all of them can be loaded explicitly resulting in an i / o - bound comparable to that of static mm_bfs . in section  [ analysis ] , however , we will argue that for most edge updates within a longer sequence , the advance value and the chunk size value for the succeeding attempt are bounded by @xmath104 implying significantly improved i / o performance .    * restricting waiting time in @xmath84 . * there is one more important detail to take care of : when adjacency - lists are brought into @xmath84 via explicit cluster accesses ( because of insufficient advance @xmath105 in the prefetching ) , these adjacency - lists will re - enter @xmath84 once more later on during the ( for these adjacency - lists by then useless ) prefetching . thus , in order to make sure that unnecessary adjacency - lists do not stay in @xmath84 forever , each entry in @xmath84 carries a time - stamp ensuring that superfluous adjacency - lists are evicted from @xmath84 after at most @xmath106 bfs levels . [ lemma : single : typeb ] for sparse graphs with @xmath1 updates , each type b update succeeding during the @xmath99-th attempt requires @xmath107 i / os . deciding whether a type b update takes place essentially requires a connected components computation , which accounts for @xmath75 i / os . within this i / o bound we can also compute a spanning tree @xmath36 of the component holding the starting vertex  @xmath8 but excluding the new edge . subsequently , there are @xmath108 attempts , each of which uses @xmath109 i / os to derive a new modified clustering based on an euler tour with increasing chunk sizes around @xmath36 . furthermore , before each attempt we need to initialize  @xmath84 and @xmath89 , which takes @xmath109 i / os per attempt . the worst - case number of i / os to ( re- ) scan adjacency - lists in @xmath84 or to explicitly fetch clusters of adjacency - lists doubles after each attempt . therefore it asymptotically suffices to consider the ( successful ) last attempt  @xmath99 , which causes @xmath110 i / os . furthermore , each attempt requires another @xmath109 i / os to pre - sort explicitly loaded clusters before they can be merged with @xmath84 using a single scan just like in mm_bfs . adding all contributions yields the claimed i / o bound of @xmath107 for sparse graphs . we split our analysis of the incremental bfs algorithm into two parts . the first ( and easy one ) takes care of type a updates :    for sparse undirected graphs with @xmath2 updates , there are at most @xmath111 type a updates causing @xmath112 i / os in total . each type a update starts with an em connected components computation causing @xmath75 i / os per update . since each node can be added to the connected component @xmath77 holding the starting vertex  @xmath8 only once , the total number of i / os spend in calls to the mr - bfs algorithm on components to be merged with @xmath77 is @xmath113 . producing the output takes another @xmath109 per update . now we turn to type b updates :    for sparse undirected graphs with @xmath2 updates , all type b updates cause @xmath114 i / os in total with high probability . recall that @xmath70 , @xmath71 , stands for the bfs level of node @xmath44 if it can be reached from the source node  @xmath8 in @xmath72 and @xmath0 otherwise . if upon the @xmath7-th update the dynamic algorithm issues an explicit fetch for the adjacency - lists of some vertex  @xmath44 kept in some cluster @xmath115 then this is because @xmath116 for the current advance  @xmath88 . note that for all other vertices @xmath117 , there is a path of length at most @xmath118 in @xmath85 , implying that @xmath119 as well as @xmath120 . having current chunk size @xmath121 , this implies @xmath122    if the @xmath7-th update needs @xmath99 attempts to succeed then , during the ( failing ) attempt @xmath123 , it has tried to explicitly access @xmath124 distinct clusters . out of these at least @xmath125 clusters carry an expected amount of at least @xmath126 adjacency - lists each . this accounts for an expected number of at least @xmath127 distinct vertices , each of them featuring @xmath128 . with probability at least @xmath129 we actually get at least half of the expected amount of distinct vertices / adjacency - lists , i.e. , @xmath130 . therefore , using the definitions @xmath131 and @xmath132 , if the @xmath7-th update succeeds within the @xmath99-th attempt we have @xmath133 with probability at least @xmath129 . let us call this event _ a large @xmath99-yield_.    since each attempt uses a new clustering with independent choices for @xmath134 , if we consider two updates  @xmath135 and  @xmath136 that succeed after the same number of attempts  @xmath99 , then both @xmath135 and @xmath136 have a large yield with probability at least @xmath129 , independent of each other . therefore , we can use chernoff bounds @xcite in order to show that out of @xmath137 updates that all succeed within their @xmath99-th attempt , at least @xmath138 of them have a large @xmath99-yield with probability at least @xmath139 for an arbitrary positive constant  @xmath140 . subsequently we will prove an upper bound on the total number of large @xmath99-yields that can occur during the whole update sequence . the quantity @xmath141 provides a global measure as for how much the bfs levels change after inclusion of the @xmath7-th edge from the update sequence . if there are @xmath142 edge inserts in total , then @xmath143 a large @xmath99-yield means @xmath144 . therefore , in the worst case there are at most @xmath145 large @xmath99-yield updates and  according to our discussion above  it needs at most @xmath146 updates that succeed within the @xmath99-th attempt to have at least @xmath147 large @xmath99-yield updates with high probability . as observed before , the dynamic algorithm will not increase its advance and chunk size values beyond @xmath148 implying @xmath149 . but then we have @xmath150 and @xmath151 for sufficiently large  @xmath0 . ] .    for the last step of our analysis we will distinguish two kinds of type b updates : those that finish using an advance value  @xmath152 ( type  b1 ) , and the others ( type  b2 ) . independent of the subtype , an update costs @xmath153 @xmath154 @xmath155 i / os by lemma  [ lemma : single : typeb ] . obviously , for an update sequence of @xmath142 edge insertions there can be at most @xmath2 updates of type  b1 , each of them accounting for at most @xmath156 i / os . as for type b2 updates we have already shown that with high probability there are at most @xmath157 updates that succeed with advance value @xmath158 . therefore , using boole s inequality , the total amount of i / os for all type  b2 updates is bounded by @xmath159 @xmath160 with high probability . combining the two lemmas of this section implies    for general sparse undirected graphs of initially @xmath0 nodes and @xmath1 edges and @xmath2 edge insertions , dynamic bfs can be solved using amortized @xmath3 i / os per update with high probability . having gone through the ideas of the incremental version , it is now close to trivial to come up with a symmetric external - memory dynamic bfs algorithm for a sequence of edge deletions : instead of pre - feeding adjacency - lists into using an _ advance _ of @xmath105 levels , we now apply a _ lag _ of @xmath105 levels . therefore , the adjacency - list for a vertex  @xmath44 is found in @xmath84 as long as the deletion of the @xmath7-th edge does not increase @xmath70 by more than  @xmath88 . otherwise , an explicit random access to the cluster containing @xmath44 s adjacency - list is issued later on . all previously used amortization arguments and bounds carry through , the only difference being that @xmath161 values may monotonically increase instead of decrease . better amortized bounds can be obtained if @xmath162 updates take place and/or @xmath69 has @xmath162 edges . then we have the potential to amortize more random accesses per attempt , which leads to larger @xmath99-yields and reduces the worst - case number of expensive updates . consequently , we can reduce the defining threshold between type  b1 and type  b2 updates , thus eventually yielding better amortized i / o bounds . details we be provided in the full version of this paper . modifications along similar lines are in order if external - memory is realized by flash disks  @xcite : compared to hard disks , flash memory can sustain many more unstructured read i / os per second but on the other hand flash memory usually offers less read / write bandwidth than hard disks . hence , in algorithms like ours that are based on a trade - off between unstructured read i / os and bulk read / write i / os , performance can be improved by allowing more unstructured read i / os ( fetching clusters ) if this leads to less overall i / o volume ( scanning hot pool entries ) . we have given the first non - trivial external - memory algorithm for dynamic bfs . even though we obtain significantly better i / o bounds than for the currently best static algorithm , there are a number of open problems : first of all , our bounds dramatically deteriorate for mixed update sequences ( edge insertions and edge deletions in arbitrary order and proportions ) ; besides oscillation effects , a single edge deletion ( insertion ) may spoil a whole chain of amortizations for previous insertions ( deletions ) . also , it would be interesting to see , whether our bounds can be further improved or also hold for shorter update sequences . finally , it would be nice to come up with a deterministic version of the modified clustering . l.  arge , g.  brodal , and l.  toma . on external - memory mst , sssp and multi - way planar graph separation . in _ proc . 8th scand . workshop on algorithmic theory ( swat ) _ , volume 1851 of _ lncs _ , pages 433447 . springer , 2000 . y.  j. chiang , m.  t. goodrich , e.  f. grove , r.  tamasia , d.  e. vengroff , and j.  s. vitter . external memory graph algorithms . in _ proc . 6th ann.symposium on discrete algorithms ( soda ) _ , pages 139149 . acm - siam , 1995 . j.  s. vitter . external memory algorithms and data structures : dealing with massive data . , pages 209271 , 2001 . revised version ( august 2007 ) available online at ` http://www.cs.purdue.edu/homes/jsv/papers/vit.io_survey.pdf ` .
we provide the first non - trivial result on dynamic breadth - first search ( bfs ) in external - memory : for general sparse undirected graphs of initially @xmath0 nodes and @xmath1 edges and monotone update sequences of either @xmath2 edge insertions or @xmath2 edge deletions , we prove an amortized high - probability bound of @xmath3 i / os per update . 
 in contrast , the currently best approach for static bfs on sparse undirected graphs requires @xmath4 i / os . 
 ulrich meyer