Domination reliability (Q426770): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C69 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C65 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68M15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C31 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6045639 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
reliability | |||
Property / zbMATH Keywords: reliability / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
domination | |||
Property / zbMATH Keywords: domination / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
decomposition | |||
Property / zbMATH Keywords: decomposition / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
inclusion-exclusion | |||
Property / zbMATH Keywords: inclusion-exclusion / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
broken circuit | |||
Property / zbMATH Keywords: broken circuit / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
cograph | |||
Property / zbMATH Keywords: cograph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
hypergraph | |||
Property / zbMATH Keywords: hypergraph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
NP-hard | |||
Property / zbMATH Keywords: NP-hard / rank | |||
Normal rank |
Revision as of 22:57, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Domination reliability |
scientific article |
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