Article ID: | iaor20173258 |
Volume: | 79 |
Issue: | 2 |
Start Page Number: | 466 |
End Page Number: | 483 |
Publication Date: | Oct 2017 |
Journal: | Algorithmica |
Authors: | Baswana Surender |
Keywords: | computers: data-structure, search, graphs, optimization |
Depth First Search (DFS) tree is a fundamental data structure for graphs used in solving various algorithmic problems. However, very few results are known for maintaining DFS tree in a dynamic environment–insertion or deletion of edges. We present the first algorithm for maintaining a DFS tree for an undirected graph under insertion of edges. For processing any arbitrary online sequence of edge insertions, this algorithm takes total