• DocumentCode
    985973
  • Title

    An O(n×log(n)) algorithm to compute the all-terminal reliability of (K5, K 2.2.2) free networks

  • Author

    Politof, T. ; Satyanarayana, Ashwin ; Tung, L.

  • Author_Institution
    Dept. of Decision Sci., Concordia Univ., Montreal, Que., Canada
  • Volume
    41
  • Issue
    4
  • fYear
    1992
  • fDate
    12/1/1992 12:00:00 AM
  • Firstpage
    512
  • Lastpage
    517
  • Abstract
    A graph is (K5, K2.2.2) free if it has no subgraph contractible to K5 or K2.2.2. The class of partial 3-trees (also known as Y-Δ graphs) is a proper subset of (K5, K 2.2.2) free graphs. Let G be a network with perfectly reliable points and edges that fail independently with some known probabilities. The all-terminal reliability R(G) of G is the probability that G is connected. Computing R(G) for a general network is NP-hard. This paper presents an O(n log n) algorithm to compute R(G) of any (K5, K2.2.2) free graphs on n points. The running time of this algorithm is O(n) if G is planar
  • Keywords
    computational complexity; graph theory; reliability theory; (K5, K2.2.2) free networks; O(n×log(n)) algorithm; Y-Δ graphs; all-terminal reliability; partial 3-trees; probability; Boolean functions; Computer networks; Fault trees; Graph theory; Polynomials; Reliability theory; Terminology;
  • fLanguage
    English
  • Journal_Title
    Reliability, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9529
  • Type

    jour

  • DOI
    10.1109/24.249577
  • Filename
    249577
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=985973