Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs

Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs

0.00 Avg rating0 Votes
Article ID: iaor20173258
Volume: 79
Issue: 2
Start Page Number: 466
End Page Number: 483
Publication Date: Oct 2017
Journal: Algorithmica
Authors:
Keywords: computers: data-structure, search, graphs, optimization
Abstract:

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 O ( n 2 ) equ1 time.

Reviews

Required fields are marked *. Your email address will not be published.