A note on boundingk-terminal reliability
Tóm tắt
A generalization of a theorem of Lomonosov and Polesskii is proved, which provides a novel method for determining upper bounds on the probability that a graph contains a Steiner tree (k-terminal reliability).
Tài liệu tham khảo
H. M. F. AboElFotoh and C. J. Colbourn, Series-parallel bounds for the two-terminal reliability problem,ORSA J. Comput. 1 (1989), 209–222.
M. O. Ball and J. S. Provan, Bounds on the reliability polynomial for shellable independence systems,SIAM J. Algebraic Discrete Methods 3 (1982), 166–181.
C. J. Colbourn,The Combinatorics of Network Reliability, Oxford University Press, Oxford, 1987.
C. J. Colbourn, Edge-packings of graphs and network reliability,Discrete Math. 72 (1988), 49–61.
C. J. Colbourn, The combinatorics of network reliability: an update,Proc. NATO Advanced Research Workshop on Topological Network Design, Copenhagen, 1989.
R. E. Gomory and T. C. Hu, Multiterminal network flows,SIAM J. Appl. Math. 9 (1961), 551–570.
R. M. Karp, Reducibility among combinatorial problems, in:Complexity of Computer Computations (R. E. Miller, J. W. Thatcher, eds) Plenum, New York, 1972, pp. 85–103.
M. V. Lomonosov, Bernoulli scheme with closure,Problems Inform. Transmission 10 (1974), 73–81.
M. V. Lomonosov and V. P. Polesskii, An upper bound for the reliability of information networks,Problems Inform. Transmission 7 (1971), 337–339.
J. S. Provan and M. O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected,SIAM J. Comput. 12 (1983), 777–788.
L. G. Valiant, The complexity of enumeration and reliability problems,SIAM J. Comput. 8 (1979), 410–421.