文献类型：期刊文献

英文题名：Maximizing k-Terminal Network Reliability in Some Sparse Graphs

作者：Zhang, Zuyuan[1];Shao, Fangming[1];Zhang, Nan[1];Niu, Yifeng[2]

机构：[1]East China Univ Sci & Technol, Sch Sci, Dept Math, Shanghai 200237, Peoples R China;[2]Chongqing Univ Posts & Telecommun, Sch Econ & Management, Chongqing 400065, Peoples R China

年份：2021

卷号：29

期号：1

起止页码：190

外文期刊名：IEEE-ACM TRANSACTIONS ON NETWORKING

收录：;EI(收录号：20204709506583);WOS:【SCI-EXPANDED(收录号:WOS:000619370600014)】；

基金：This work was supported in part by the National Natural Science Foundation of China (Project No.71601072); and in part by the Scientific and Technological Research Program of Chongqing Municipal Education Commission under Grant KJQN201900634.

语种：英文

外文关键词：Telecommunication network reliability; Computer network reliability; Reliability theory; Reliability engineering; Heuristic algorithms; < italic xmlns; ali=" http; www; niso; org; schemas; ali; 1; 0; " xmlns; mml=" http; www; w3; org; 1998; Math; MathML" xmlns; xlink=" http; www; w3; org; 1999; xlink" xmlns; xsi=" http; www; w3; org; 2001; XMLSchema-instance" > k< italic> -terminal network reliability; maximization; network topology; sparse graphs

摘要：k-terminal network reliability is the probability that k terminal vertices are connected given that edges in the network fail independently while vertices do not fail. It depends on the distribution of these terminal vertices as well as network topology. The problem of computing k-terminal reliability is NP-hard. Previous literature mainly focus on designing efficient algorithms to compute it in different graphs, but are lacking in the analysis for optimal distribution of k terminal vertices in sparse graphs, within which those with n nodes and m edges, where m <= n + 1 , are most basic classes. Hence, it is of great significance to investigate the optimal distribution of terminal vertices in these classes of graphs before considering general cases. In this paper, we prove that k-terminal network reliability obtains the maximum if k terminal vertices induce a connected subgraph. Further, we give equations of maximum reliability for all possible graphs in the above classes. The experiments illlustrate the variation, with several parameters and according to our theoretical results, of maximal k-terminal reliability, and provide observations for graphs with any number of edges.