A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR ALL-TERMINAL NETWORK RELIABILITY

被引：19

作者：

Guo, Heng ^{[1
]}

Jerrum, Mark ^{[2
]}

机构：

[1] Univ Edinburgh, Sch Informat, Edinburgh EH8 9AB, Midlothian, Scotland

[2] Queen Mary Univ London, Sch Math Sci, London E1 4NS, England

来源：

SIAM JOURNAL ON COMPUTING | 2019年 / 48卷 / 03期

基金：

英国工程与自然科学研究理事会;

关键词：

network reliability; approximate counting; randomized algorithms; COMPUTATIONAL-COMPLEXITY;

D O I：

10.1137/18M1201846

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that in an undirected graph, assuming each edge fails independently, the remainder of the graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak [Random Structures Algorithms, 44 (2014), pp. 201-223] that the expected running time of the "cluster-popping" algorithm in bidirected graphs is bounded by a polynomial in the size of the input.

引用

页码：964 / 978

页数：15

共 34 条

[1] Hodge theory for combinatorial geometries
Adiprasito, Karim
Huh, June
Katz, Eric
[J]. ANNALS OF MATHEMATICS, 2018, 188 (02) : 381 - 452
[2] [Anonymous], 1993, Matroid Theory
[3] [Anonymous], 1993, LONDON MATH SOC LECT
[4] COMPLEXITY OF NETWORK RELIABILITY COMPUTATIONS
BALL, MO
[J]. NETWORKS, 1980, 10 (02) : 153 - 165
[5] CALCULATING BOUNDS ON REACHABILITY AND CONNECTEDNESS IN STOCHASTIC NETWORKS
BALL, MO
PROVAN, JS
[J]. NETWORKS, 1983, 13 (02) : 253 - 278
[6] COMPUTATIONAL-COMPLEXITY OF NETWORK RELIABILITY-ANALYSIS - AN OVERVIEW
BALL, MO
[J]. IEEE TRANSACTIONS ON RELIABILITY, 1986, 35 (03) : 230 - 239
[7] Cohn H, 2002, ELECTRON J COMB, V9
[8] Colbourn CJ., 1987, COMBINATORICS NETWOR
[9] Inapproximability of the Tutte polynomial
Goldberg, Leslie Ann
Jerrum, Mark
[J]. INFORMATION AND COMPUTATION, 2008, 206 (07) : 908 - 929
[10] THE COMPLEXITY OF COMPUTING THE SIGN OF THE TUTTE POLYNOMIAL
Goldberg, Leslie Ann
Jerrum, Mark
[J]. SIAM JOURNAL ON COMPUTING, 2014, 43 (06) : 1921 - 1952

← 1 2 3 4 →