Estruturas de dados retroativas: aplicações na dinamização de algoritmos

Abstract

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.