This paper studies the Dynamic Localization Problem (DLP) in graphs, formulated by Chung, Graham, and Saks [CGS89] in 1989. The Dynamic Localization Problem is a combinatorial optimization problem within discrete mathematics, using a graph G = (V, E) as its system. A source, initially located at a vertex of G, can move to sequentially fulfill a list of requirements located at the vertices of the graph, minimizing the cost of moving and fulfilling them. We study two scenarios: Off-line, where the list of requirements to be fulfilled is fully available from the beginning, and Online, where the list of requirements is revealed progressively, and each movement of the source must be decided with partial information about the future.

In the offline context, we studied fundamental structural properties that describe the optimal behavior for the LDP and designed an optimal algorithm based on the algorithm design paradigm known as dynamic programming. We theoretically justified the correctness of this algorithm and calculated its time complexity, resulting in O(n^2 k), where n is the number of vertices in the system's graph, and k is the number of requirements to be solved. We implemented this algorithm in the Python programming language to use it as a benchmark for comparing the performance of online algorithms.

In the online case, following the work of Chung, Graham, and Saks [CGS87, CGS89], we introduced a parameter in graphs called the Window Index (Windex), which measures the smallest window value k for which an optimal LDP algorithm exists in G that works by knowing only the next k requirements to be solved. In other words, Windex essentially measures how much information about the future is needed to ensure the existence of an algorithm that finds optimal solutions. We studied graphs with finite and infinite Windex by calculating the Windex of particular graph classes. We also analyzed the correctness and computational complexity of two algorithms:

The Greedy Algorithm (Window 1): which uses the greedy paradigm in its design and guarantees an approximation ratio of 2 for the PLD in any graph.

The Windex 2 Algorithm (Window 2): which is optimal for Windex 2 graphs and bases its design on the Unique Steiner Triplet Property (USTP).

Based on the characterization by Chung, Graham, and Saks [CGS87], we proved that graphs with Windex 2 are exactly the medium-sized graphs, which includes structures such as trees, square grids, and hypercubes.

Finally, we conducted an experimental section where we evaluated the performance of the Greedy Algorithm and the Windex 2 Algorithm on different graphs, basing our choice on the Windex value of the selected graphs and varying the edge density of the graphs. The algorithms were implemented in the Python programming language. In the case of the Windex 2 Algorithm, our results provide empirical evidence for the conjecture made by Chung, Graham, and Saks [CGS89] regarding the existence of an algorithm with a window of 2 and an approximation ratio of 3/2. Furthermore, based on the experiments, we can conclude that the Windex 2 Algorithm consistently outperforms the Greedy Algorithm, especially on graphs with Windex 2 or graphs with high density, and that the graph's structure and density have a direct impact on the algorithms' performance.