In this paper, we address the decentralized and parallel construction of rigid graphs in the plane that optimize an edgeweighted objective function under cardinality constraints. Two auction-based algorithms to solve this problem in a decentralized fashion are first proposed. Centered around the notion of leader election, the first approach finds an optimal solution through a greedy bidding, while the second approach provides a sub-optimal solution which reduces complexity according to a sliding mode parameter. Then, by exploiting certain local structural properties of graph rigidity, a parallelization to build a portion of the optimal solution in constant time is derived. A theoretical characterization of algorithm performance is provided together with complexity analysis. Finally, simulation results are presented to corroborate the theoretical findings.
Gasparri, A., Williams R., K., Priolo, A., & Sukhatme, G.S. (2015). Decentralized and Parallel Constructions for Optimally Rigid Graphs in R^2. IEEE TRANSACTIONS ON MOBILE COMPUTING, 14(11), 2216-2228 [10.1109/TMC.2015.2393856].