The backup 2-center and backup 2-median problems on trees

Hung Lung Wang, Bang Ye Wu, Kun Mao Chao*

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

12 引文 斯高帕斯(Scopus)

摘要

In this paper, we are concerned with the problem of deploying two servers in a tree network, where each server may fail with a given probability. Once a server fails, the other server will take full responsibility for the services. Here, we assume that the servers do not fail simultaneously. In the backup 2-center problem, we want to deploy two servers at the vertices such that the expected distance from a farthest vertex to the closest functioning server is minimum. In the backup 2-median problem, we want to deploy two servers at the vertices such that the expected sum of distances from all vertices to the set of functioning servers is minimum. We propose an O(n)-time algorithm for the backup 2-center problem and an O(n log n)-time algorithm for the backup 2-median problem, where n is the number of vertices in the given tree network.

原文英語
頁(從 - 到)39-49
頁數11
期刊Networks
53
發行號1
DOIs
出版狀態已發佈 - 2009 1月
對外發佈

ASJC Scopus subject areas

  • 資訊系統
  • 電腦網路與通信

指紋

深入研究「The backup 2-center and backup 2-median problems on trees」主題。共同形成了獨特的指紋。

引用此