Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2011
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/1103.3854 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911296868319232 |
|---|---|
| author | Dohmen, Klaus Tittmann, Peter |
| author_facet | Dohmen, Klaus Tittmann, Peter |
| contents | We propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulae for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1103_3854 |
| institution | arXiv |
| publishDate | 2011 |
| record_format | arxiv |
| spellingShingle | Domination Reliability Dohmen, Klaus Tittmann, Peter Combinatorics Discrete Mathematics Probability 05C30, 05C31 (Primary) 62N05, 68M15, 90B25 (Secondary) We propose a new network reliability measure for some particular kind of service networks, which we refer to as domination reliability. We relate this new reliability measure to the domination polynomial of a graph and the coverage probability of a hypergraph. We derive explicit and recursive formulae for domination reliability and its associated domination reliability polynomial, deduce an analogue of Whitney's broken circuit theorem, and prove that computing domination reliability is NP-hard. |
| title | Domination Reliability |
| topic | Combinatorics Discrete Mathematics Probability 05C30, 05C31 (Primary) 62N05, 68M15, 90B25 (Secondary) |
| url | https://arxiv.org/abs/1103.3854 |