On the complexity of the minimum and maximum global snapshot problems

L. B. Chen*, I-Chen Wu

*Corresponding author for this work

Research output: Contribution to journalConference article

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 network flow (MCNF) problem, here defined as the well-known maximum network flow problem with m = qq(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.

Original languageEnglish
Pages (from-to)38-41
Number of pages4
JournalProceedings - IEEE Computer Society's International Computer Software and Applications Conference
DOIs
StatePublished - 1 Jan 1997
EventProceedings of the 1997 21st Annual International Computer Software & Applications Conference, COMPSAC'97 - Washington, DC, USA
Duration: 13 Aug 199715 Aug 1997

Fingerprint Dive into the research topics of 'On the complexity of the minimum and maximum global snapshot problems'. Together they form a unique fingerprint.

Cite this