Domination reliability (Q426770): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1103.3854 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:35, 18 April 2024
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