On the time complexity of minimum and maximum global snapshot problems

檔案

日期

1998-08-17

類型

期刊名稱

INFORMATION PROCESSING LETTERS

卷期與頁次

第 67 卷第 3 期,頁 151–156

ISSN

0020-0190

語言

英文

摘要

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. (C) 1998 Elsevier Science B.V. All rights reserved.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chen, L., & Wu, I. (1998). On the time complexity of minimum and maximum global snapshot problems. INFORMATION PROCESSING LETTERS, 67(3), 151–156. https://ir.lib.nycu.edu.tw/handle/11536/32452

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/32452