On the time complexity of minimum and maximum global snapshot problems

Loon Been Chen, I-Chen Wu*

*Corresponding author for this work

Research output: Contribution to journalArticle

2 Scopus citations

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 = Θ(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)151-156
Number of pages6
JournalInformation Processing Letters
Volume67
Issue number3
DOIs
StatePublished - 17 Aug 1998

Keywords

  • Computational complexity
  • Distributed systems
  • Error detection
  • Global snapshot

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

  • Cite this