Resumo:
The retroactivity in programming is the study of a modification in a timeline for a data structure and the effects that this modification exerts throughout its existence. In general,
the analysis and implementation tend to be more costly computationally, because a modification
on these data structure in the past can generate a cascade effect through all the data
structure timeline. The concept of retroactivity generates tools and structures that optimize
the solutions facing these temporal problems. This type of data structure can be used in,
for example, shortest path algorithms, security applications, and geometric problems. In
this thesis, we have the theoretical subsidies about these data structures, a detailed material
about the implementation of this structures, using retroactivity, and the implementation of
some problems that retroactivity can be used, for example, the fully dynamic minimum
spanning tree problem. For each data structure, we executed practical tests about this data
retroactive data structures and a comparison between these solutions and other approaches.
The tests showed that the retroactive implementations proposed by Demaine et. al (2007)
[13] obtained the best results from a temporal point of view. It was proposed two algorithms
which used the retroactivity concepts inside its development: the fully retroactive minimum
spanning tree and the single source dynamic shortest path problem in dynamic graphs. Let m
be data structure’s timeline, V(G) and A(G) the sets of vertices and edges from graph G. We
reached an amortized time complexity O(
√
m· lg |V(G)|) per query/update operation in the
fully retroactive minimum spanning tree algorithm. The algorithm to solve the single source
dynamic shortest path problem in dynamic graphs proposed by Sunita et. al [52] obtained
a time complexity O(|A(G)| · lg |V(G)|) per modification using a non-oblivious retroactive
priority queue.
