<p>This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for.</p>

<p>You could also try <a href="http://www-lih.univ-lehavre.fr/~guinand/Enseignement/RI2D/References/2003_bhadra-ferreira_complexity_connected_components_evolving_graphs_computation_multicast_trees_dynamic_networks.pdf" rel="nofollow">Bhadra &amp; Ferreira</a>, they're probably getting a bit off-topic for what you want, but they do have references to other material that could be useful.</p>

CC BY-SA 3.0
2012-06-11T13:37:36.543Z
2012-06-11T13:37:36.543Z
Luke Mathieson
<p>The Vertex updates can be handled using edge updates as follows (Although a bit
inefficient as it makes deg(u) calls to edge update function):</p>

<pre><code>AddVertex(G,u,Adj(u)):- 
  /* Adj(u) is the vertices adjacent to u after adding u */  
  For each v in Adj(u) do 
    AddEdge(G, (u,v))

DeleteVertex(G,u):- 
  For each v in Adj(u) do
    DeleteEdge(G, (u,v)) 
</code></pre>

<p>Thorup et. Al's running time analysis states that their update time is amortised 
time per edge update. So, It doesn't directly imply any poly. logarithmic update
time result under vertex updates. </p>

<p>There are some works where the update operation supports vertex/addition
deletion as well. In [1] for Dynamic All Pairs Shortest Paths problem, they
basically allow updating edges incident on a vertex by specifying the new 
weights. We can update them all to +infinity for deleting a vertex and similarly
for adding a vertex.</p>

<p>You might find the references [2], and [3] helpful if you are just starting with
dynamic graph algorithms. [2] gives a good high level idea of current 
approaches to dynamic connectivity problem.</p>

<p><strong>References</strong></p>

<ol>
<li><p>A new approach to dynamic All pairs shortest paths, Demetrescu. et. Al, JACM 2004 Voume 51 
issue 6, 2004</p></li>
<li><p><a href="https://www.imsc.res.in/~dsmeet/Dyn-algo-I.pptx" rel="nofollow">Slide</a> of Talk on Dynamic graph Algorithms by Dr. Surender Baswana in "Recent advances in data structures and algorithms" workshop held at IMSc, Chennai. </p></li>
<li><p>Camil Demetrescu and Pino Italiano, Dynamic graphs, Handbook on Data Structures and Applications, Chapter 36. Dinesh Mehta and Sartaj Sahni (eds.), CRC Press Series, in Computer and Information Science, January 2005.<a href="http://www.diku.dk/PATH05/CRC-book1.pdf" rel="nofollow"> [Draft</a> (pdf)]</p></li>
</ol>

CC BY-SA 3.0
2012-06-12T00:36:32.887Z
2012-06-12T00:36:32.887Z
rizwanhudda
<p>Holm et. al's algorithm works with an arbitrary number of vertices, though it isn't so clear from the description.  The main difficulty in their presentation is how they label the levels of the forest.  If instead of setting the largest level forest to $F_{lg(n)}$, you start counting from $F_0$ up and modify invariant 2 such that every tree in level i has size at most $\frac{n}{2^i}$ instead of $2^i$, then there is no longer a bound on the number of vertices in the graph and you can freely insert and delete them as you choose.</p>

<p>For an example implementation of this (in JavaScript) you can take a look a the following GitHub repository:</p>

<p><a href="https://github.com/mikolalysenko/dynamic-forest" rel="nofollow">https://github.com/mikolalysenko/dynamic-forest</a></p>

CC BY-SA 3.0
2013-12-20T01:06:28.687Z
2013-12-20T01:06:28.687Z
Mikola
<p>I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if my terminology is not exactly right. </p>

<p>I have a database system where user can add/remove/move objects by creating/deleting and altering relationships. As such, I can see the objects as been vertices in a graph and the relationships been edges and edges can be weighted depending on the type of relationships (either composition, association, or aggregation). </p>

<p>From the user's point of view, adding a new element can be a single click and underneath the hood, the program creates a graph of objects linked by relationships. This graph, is then added to the main graph that defines the entire database. Removing an element, would be the reverse where links/edges are disconnected and the graph becomes two disjoint graphs where 1 is the database, and the other consists of vertices formed by the element and its sub elements.</p>

<p>I need a really quick way to determine when I have a disjoint graphs and when 2 disjoint graphs becomes 1 again. I had a brief look at Holm, de Lichtenberg, and Thorup (<a href="http://dl.acm.org/citation.cfm?id=502095">2001</a>; <a href="http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/polylogarithmic.pdf">pdf</a>). It seems like the way to go, but the author did mention they are only considering a graph with fixed number of vertices. Just wondering do algorithms usually extend themselves to adding/removal of vertices by just performing the adding of edges incrementally? Or has there been works that tailors specifically for such scenario? </p>

<ds.algorithms><graph-theory><dynamic-algorithms>
Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion
Thuan Seah Tan
# Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

(Asked by: username_0 on 2012-06-11)

I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if my terminology is not exactly right.

I have a database system where user can add/remove/move objects by creating/deleting and altering relationships. As such, I can see the objects as been vertices in a graph and the relationships been edges and edges can be weighted depending on the type of relationships (either composition, association, or aggregation).

From the user's point of view, adding a new element can be a single click and underneath the hood, the program creates a graph of objects linked by relationships. This graph, is then added to the main graph that defines the entire database. Removing an element, would be the reverse where links/edges are disconnected and the graph becomes two disjoint graphs where 1 is the database, and the other consists of vertices formed by the element and its sub elements.

I need a really quick way to determine when I have a disjoint graphs and when 2 disjoint graphs becomes 1 again. I had a brief look at Holm, de Lichtenberg, and Thorup ([2001](http://dl.acm.org/citation.cfm?id=502095); [pdf](http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/polylogarithmic.pdf)). It seems like the way to go, but the author did mention they are only considering a graph with fixed number of vertices. Just wondering do algorithms usually extend themselves to adding/removal of vertices by just performing the adding of edges incrementally? Or has there been works that tailors specifically for such scenario?

**Tags:** ds.algorithms, graph-theory, dynamic-algorithms


---

## 3 answers

### Answer by username_1 on 2012-06-11. Score: 4

This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for.

You could also try [Bhadra & Ferreira](http://www-lih.univ-lehavre.fr/~guinand/Enseignement/RI2D/References/2003_bhadra-ferreira_complexity_connected_components_evolving_graphs_computation_multicast_trees_dynamic_networks.pdf), they're probably getting a bit off-topic for what you want, but they do have references to other material that could be useful.


---

### Answer by username_2 on 2012-06-12. Score: 1

The Vertex updates can be handled using edge updates as follows (Although a bit
inefficient as it makes deg(u) calls to edge update function):
AddVertex(G,u,Adj(u)):- 
  /* Adj(u) is the vertices adjacent to u after adding u */  
  For each v in Adj(u) do 
    AddEdge(G, (u,v))

DeleteVertex(G,u):- 
  For each v in Adj(u) do
    DeleteEdge(G, (u,v)) 

Thorup et. Al's running time analysis states that their update time is amortised 
time per edge update. So, It doesn't directly imply any poly. logarithmic update
time result under vertex updates. 
There are some works where the update operation supports vertex/addition
deletion as well. In [1] for Dynamic All Pairs Shortest Paths problem, they
basically allow updating edges incident on a vertex by specifying the new 
weights. We can update them all to +infinity for deleting a vertex and similarly
for adding a vertex.
You might find the references [2], and [3] helpful if you are just starting with
dynamic graph algorithms. [2] gives a good high level idea of current 
approaches to dynamic connectivity problem.
References

A new approach to dynamic All pairs shortest paths, Demetrescu. et. Al, JACM 2004 Voume 51 
issue 6, 2004
Slide of Talk on Dynamic graph Algorithms by Dr. Surender Baswana in "Recent advances in data structures and algorithms" workshop held at IMSc, Chennai. 
Camil Demetrescu and Pino Italiano, Dynamic graphs, Handbook on Data Structures and Applications, Chapter 36. Dinesh Mehta and Sartaj Sahni (eds.), CRC Press Series, in Computer and Information Science, January 2005. [Draft (pdf)]


---

### Answer by username_3 on 2013-12-20. Score: 0

Holm et. al's algorithm works with an arbitrary number of vertices, though it isn't so clear from the description. The main difficulty in their presentation is how they label the levels of the forest. If instead of setting the largest level forest to $F\_{lg(n)}$, you start counting from $F\_0$ up and modify invariant 2 such that every tree in level i has size at most $\frac{n}{2^i}$ instead of $2^i$, then there is no longer a bound on the number of vertices in the graph and you can freely insert and delete them as you choose.

For an example implementation of this (in JavaScript) you can take a look a the following GitHub repository:

<https://github.com/mikolalysenko/dynamic-forest>


---

