Algorithms of placing recovery points (Q1111383)

We study the complexity of placing recovery points in computer programs, so that the roll-back time is minimized. The roll-back time corresponds to the recomputation time involved from the previous correct point. Here we give \(O(n^ 2)\) time algorithms for placing recovery points when the underlying program model is either a path tree or a rooted tree. We also show that the problem is NP-complete when the underlying program model is a directed graph.