wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

network_reliability (643B)

      1 # Network reliability
      2 
      3 The problem is called *network reliability*. You have a
      4 graph G and a set T of terminals. You want to count the number of
      5 subgraphs of G in which the vertices of T are connected.
      6 
      7 Can be posed for [directed_graphs] or [undirected_graphs]
      8 
      9 - [st_reliability] when |T| = 2
     10 - [multi_terminal_network_reliability] for larger T
     11 - [all_terminal_network_reliability] when T contains all vertices
     12 
     13 Can also want to count the number of [subgraphs] that are not connected (makes a difference for [approximation]): [network_unreliability]
     14 
     15 [FPRAS]: [network_reliability_fpras]
     16 
     17 Up: [graph]
     18 
     19 See also: [pqe], [reliability_database]