On the Feasibility of Maintenance Algorithms in Dynamic Graphs
Near ubiquitous mobile computing has led to intense interest in dynamic graph theory. This provides a new and challenging setting for algorithmic and complexity theory. For any graph-based problem, the rapid evolution of a (possibly disconnected) graph over time naturally leads to the important complexity question: is it better to calculate a new solution from scratch or to adapt the known solution on the prior graph to quickly provide a solution of guaranteed quality for the changed graph? In this paper, the authors demonstrate that the former is the best approach in some cases, but that there are cases where the latter is feasible.