On the complexity of the minimum and maximum global snapshot problems
L.B. Chen, I‐Chen Wu · 2002
Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj (1993) and Chen and Wu (1996), have shown that the minimum and maximum global snapshot problems are linear-time reducible to the maximum constant-ratio network flow (MCNF) problem, here defined as the well-known maximum network flow problem with m=/spl Theta/(n), where m is the number of edges and n is the number of vertices in the given flow network. The authors show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, one can conclude that the global snapshot problems are "as difficult as" the MCNF problem in terms of time complexity.