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.

, , , ,
Information Processing Letters
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