Questions tagged [dynamic-algorithms]

Questions about algorithms that deals with changing input data. Given a class of input objects, find efficient algorithms and data structures to answer a certain query about a set of input objects each time the input data is modified, i.e., objects are inserted or deleted.

Filter by
Sorted by
Tagged with
3 votes
2 answers
1k views

Find 1s in almost all 0 array using comparisons only

So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python): ...
user555076's user avatar
2 votes
1 answer
88 views

Optimal graph data structure for set of points that allows dynamic updates

We aim to optimize the execution of a specific task. Consider a set, P, containing N 2D points. A new query point, p1, is introduced, and the objective is to identify the nearest point in P to p1. If ...
Apurv Mishra's user avatar
1 vote
0 answers
45 views

How to compute the updated shortest paths given a set of edge insertions efficiently?

Let $G = (V, E)$ be a graph with edge weights $w: E \rightarrow \mathbb{R} \cup \{\infty\}$. Let $P := \{(a_i, b_i, w_i)\}$ be a set of tuples of nodes $a_i, b_i \in V$ with shortest distance $w_i$ ...
Sebastian Schmidt's user avatar
1 vote
0 answers
224 views

State-of-the-Art techniques on dynamic shortest path computations

Suppose that I would like to find the shortest path between two vertices in a dynamic graph, where the cost function of an edge changes occasionally. I understand that an efficient algorithm to target ...
San Yeung's user avatar
29 votes
3 answers
15k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
Rontogiannis Aristofanis's user avatar