Domination reliability (Q426770)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Domination reliability |
scientific article; zbMATH DE number 6045639
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Domination reliability |
scientific article; zbMATH DE number 6045639 |
Statements
Domination reliability (English)
0 references
12 June 2012
0 references
Summary: In this paper, 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 formulæ 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.
0 references
reliability
0 references
domination
0 references
decomposition
0 references
inclusion-exclusion
0 references
broken circuit
0 references
cograph
0 references
hypergraph
0 references
NP-hard
0 references
