How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-Hard

DOI10.1137/12086594XzbMath1304.93018arXiv1202.3167OpenAlexW1976631094MaRDI QIDQ5173258

Alex Olshevsky, Blondel, Vincent D.

Publication date: 9 February 2015

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.3167

zbMATH Keywords

computational complexityswitched systemsconsensus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decentralized systems (93A14) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Related Items (7)

Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms ⋮ Tight bound for deciding convergence of consensus systems ⋮ Efficient Algorithms for the Consensus Decision Problem ⋮ On primitivity of sets of matrices ⋮ Random asynchronous iterations in distributed coordination algorithms ⋮ Gossip over holonomic graphs ⋮ Phase transitions in the Ising model on a hierarchical random graph based on the triangle

This page was built for publication: How to Decide Consensus? A Combinatorial Necessary and Sufficient Condition and a Proof that Consensus is Decidable but NP-Hard