A reliability-improving graph transformation with applications to network reliability (Q3989403)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 34488
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A reliability-improving graph transformation with applications to network reliability |
scientific article; zbMATH DE number 34488 |
Statements
A reliability-improving graph transformation with applications to network reliability (English)
0 references
28 June 1992
0 references
probabilistic flow
0 references
highly connected nets
0 references
reliability
0 references
threshold net
0 references
0.7928491234779358
0 references
0.7915201187133789
0 references
0.7873752117156982
0 references
For a network (graph) \(G\) of \(n\) terminals (nodes) connected by \(e\) unreliable lines (edges) --- no loops and no multiple edges --- the overall reliability \(R\) is of main interest: that each terminal has at least one working path to each other terminal. This paper considers the case of a nearly fully connected net: each pair of terminals connected by a direct line except for at most \(n/2\) of the pairings, where each line has independently the same fixed working probability \(p\) of being in full operating mode and \(1-p\) of being completely disrupted, independent of load and time. It is shown that for any \(p\) the highest reliability has net \(H\) with the same number of nodes and edges, but not two excepted edges having a common node. For proof, \(G\) is stepwise transformed into \(H\), holding \((n,e)\) constant, such that \(R\) increases with every step. Each step, called ``swinging surgery'', switches only some lines to one selected node \(v\) from another one \(u\), whose neighbourhood contains all the neighbours of \(v\) and is sufficiently large. An additional condition on the interconnection of the neighbourhoods of \(u\) and \(v\) guarantee that the increase is strongly monotone, as in the case at hand. The last section shows that from any simple \(G\) a so-called threshold net (graph) \(T\) can be derived by similar non-increasing steps: \(T\) is minimal for \((n,e)\), and if \(G\) is connected, so is \(T\). An algorithm for \(T\) is presented. This latter result is proposed for resolving a conjecture (of Boesch et al.) concerning existence and structural aspect of the ``uniformly worst'' (i.e. for each \(p\) most unreliable) graph with same \((n,e)\).
0 references