Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a connected component.

I am interested in finding the maximal connected component span.

In the example below, there are three connected components over time (blue rectangles): $\{a,b,c\}$ from time $0$ time to $5$; $\{d,e\}$ on the same time interval, and $\{a,b,c,d,e\}$ from $5$ to $10$. They have span $15$, $10$ and $25$, respectively, hence the wanted result is $25$.

                  connected components in a link stream

Dynamic connectivity algorithms make it possible to compute the connected components over time, and so they provide a solution to the above problem. They typically need polylog time per edge addition or removal, with complex data structures.

Is there a faster way to compute the maximal connected component span?

In particular, suppose we know the dynamics in advance: we have, for each edge, the list of times at which it is added and removed. Therefore, we do not have to process edge additions and removals in chronological order. Does this make the above problem simpler?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.