Questions tagged [dynamic-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
17
votes
1answer
720 views

What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion? I read some papers on the dynamic transitive closure problem with ...
15
votes
0answers
1k views

What is the fastest deterministic algorithm for incremental DAG reachability?

As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
8
votes
2answers
782 views

What is the initialization time of a link-cut tree?

Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
8
votes
3answers
1k views

Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

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 ...