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].
Titolo: | Decentralized and Parallel Constructions for Optimally Rigid Graphs in R^2 | |
Autori: | ||
Data di pubblicazione: | 2015 | |
Rivista: | ||
Citazione: | 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]. | |
Handle: | http://hdl.handle.net/11590/138981 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |