Title: On the complexity of the minimum and maximum global snapshot problems
Authors: Chen, LB
Wu, IC
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
Issue Date: 1997
Abstract: 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 net work 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.
URI: http://hdl.handle.net/11536/19612
http://dx.doi.org/10.1109/CMPSAC.1997.624733
ISBN: 0-8186-8106-3
ISSN: 0730-3157
DOI: 10.1109/CMPSAC.1997.624733
Journal: COMPSAC 97 : TWENTY-FIRST ANNUAL INTERNATIONAL COMPUTER SOFTWARE & APPLICATIONS CONFERENCE
Begin Page: 38
End Page: 41
Appears in Collections:Conferences Paper


Files in This Item:

  1. A1997BJ50U00006.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.