Lower bounds on two-terminal network reliability (Q1116878)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Lower bounds on two-terminal network reliability
scientific article

    Statements

    Lower bounds on two-terminal network reliability (English)
    0 references
    0 references
    0 references
    1988
    0 references
    Computing the probability that two nodes in a probabilistic network are connected is a well-known computationally difficult problem. Two strategies are devised for obtaining lower bounds on the connection probability for two terminals. The first improves on the Kruskal-Katona bound by using efficient computations of small pathsets. The second strategy employs efficient algorithms for finding edge-disjoint paths. The resulting bounds are compared; while the edge-disjoint path bounds typically outperform the Kruskal-Katona bounds, they do not always do so. Finally, a method is outlined for developing a uniform bound which combines both strategies.
    0 references
    network reliability
    0 references
    two-terminal reliability
    0 references
    topological design
    0 references
    probabilistic network
    0 references
    lower bounds
    0 references
    connection probability
    0 references
    edge- disjoint paths
    0 references
    Kruskal-Katona bounds
    0 references

    Identifiers