Name
Title | ||
|---|---|---|
Evaluating Network Reliability and 2-Edge-Connected Reliability in Linear Time for Bounded Pathwidth Graphs |
Abstract | ||
|---|---|---|
This paper presents a decomposition method for computing the 2-edge-connected reliability of undirected networks. This reliability is defined as the probability that all the vertices of a given graph G are 2-edge-connected, when edges fail independently with known probabilities. The principle of this method was introduced by Rosenthal in 1977 [1]. For the all terminal reliability problem it consists in enumerating specific state classes of some subnetworks. These classes are represented by the partitions of the boundary sets. For the 2-edge-connected reliability problem these classes are represented by labeled forests whose nodes are the partition blocks and some ``unidentified'' blocks. Our implementation uses a vertex linear ordering. The computational complexity depends on the number of classes, which depends on the vertex separation number of a given vertex linear ordering. Our computational results show the efficiency of this method when the vertex separation number is smaller than 7. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s004530010022 | Algorithmica |
Keywords | Field | DocType |
Key words. Network reliability,2-Edge-connectivity,Network decomposition,Boundary set,Pathwidth. | Discrete mathematics,Combinatorics,Vertex (geometry),Vertex (graph theory),Decomposition method (constraint satisfaction),Reliability (computer networking),Pathwidth,Time complexity,Mathematics,Computational complexity theory,Bounded function | Journal |
Volume | Issue | ISSN |
27 | 3 | 0178-4617 |
Citations | PageRank | References |
4 | 0.62 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Corinne Lucet | 1 | 99 | 8.51 |
| Jean-francois Manouvrier | 2 | 5 | 0.97 |
| Jacques Carlier | 3 | 4 | 0.62 |