loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
COMPSAC '97 - 21st International Computer Software and Applications Conference
On the Complexity of the Minimum and Maximum Global Snapshot Problems
Washington, DC
August 11-August 15
ISBN: 0-8186-8105-5
L.B. Chen, National Chiao Tung University
I.C. Wu, National Chiao Tung University
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 = \Theta(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.
Citation:
L.B. Chen, I.C. Wu, "On the Complexity of the Minimum and Maximum Global Snapshot Problems," compsac, pp.38, COMPSAC '97 - 21st International Computer Software and Applications Conference, 1997
Usage of this product signifies your acceptance of the Terms of Use.