1994-07-12
Optimal coteries and voting schemes
Publication
Publication
Information Processing Letters , Volume 51 - Issue 1 p. 1- 6
We consider coteries (i.e. intersecting, Sperner systems) on arbitrary networks with given node reliability, which maximize the network availability (i.e. the probability that the set of operating nodes has a connected subgraph which contains a set from the coterie). We show that the singleton coterie is always optimal on any network when the node reliability is p≤ 1 2. For p≥ 1 2, we give optimal coteries for the complete multipartite networks. The resulting optimal coteries when restricted to a special subclass of complete bipartite networks are shown to exceed the availability of any voting scheme, for p 1 2.
Additional Metadata | |
---|---|
, , , , | |
doi.org/10.1016/0020-0190(94)00064-6 | |
Information Processing Letters | |
Organisation | School of Computer Science |
Diks, K. (Krzysztof), Kranakis, E, Krizanc, D. (Danny), Mans, B. (Bernard), & Pelc, A. (Andrzej). (1994). Optimal coteries and voting schemes. Information Processing Letters, 51(1), 1–6. doi:10.1016/0020-0190(94)00064-6
|