Dynamic Problems on Undirected Graphs

Abstract

In many applications of graph algorithms, including communication networks, VLSI design, graphics, and assembly planning, graphs are subject to discrete changes, such as additions or deletions of edges or vertices. In the last two decades there has been a growing interest in such dynamically changing graphs, and a whole body of algorithms and data structures for dynamic graphs has been discovered. This paper presents two different data structures that maintain properties of dynamically changing trees: topology trees, ET trees. Next, in the course of the presentation, it was also highlighted how these techniques have been applied to solve the fully dynamic connectivity and/or minimum spanning tree problems, and which update and query bounds can be achieved when they are deployed.