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].

Decentralized and Parallel Constructions for Optimally Rigid Graphs in R^2

GASPARRI, ANDREA
;
2015

Abstract

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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/138981
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 5
social impact