TY - JOUR

T1 - On the time complexity of minimum and maximum global snapshot problems

AU - Chen, Loon Been

AU - Wu, I-Chen

PY - 1998/8/17

Y1 - 1998/8/17

N2 - Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj, Chen and Wu, 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 = Θ(n), where m is the number of edges and n is the number of vertices in the given flow network. In this paper we show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, we can conclude that the global snapshot problems are "as difficult as" the MCNF problem in terms of time complexity.

AB - Deriving the minimum and maximum global snapshots is very useful for some error detection problems in distributed programs. Several researchers, e.g., Groselj, Chen and Wu, 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 = Θ(n), where m is the number of edges and n is the number of vertices in the given flow network. In this paper we show in a reverse way that the MCNF problem is also linear-time reducible to these global snapshot problems. Thus, we can conclude that the global snapshot problems are "as difficult as" the MCNF problem in terms of time complexity.

KW - Computational complexity

KW - Distributed systems

KW - Error detection

KW - Global snapshot

UR - http://www.scopus.com/inward/record.url?scp=0012703396&partnerID=8YFLogxK

U2 - 10.1016/S0020-0190(98)00100-8

DO - 10.1016/S0020-0190(98)00100-8

M3 - Article

AN - SCOPUS:0012703396

VL - 67

SP - 151

EP - 156

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 3

ER -