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

Gasparri, Andrea; Williams R., K; Priolo, A; Sukhatme, G. S.

doi:10.1109/TMC.2015.2393856

Benvenuti nell'Anagrafe della Ricerca d'Ateneo

La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.

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:	GASPARRI, ANDREA (Corresponding) Williams R. K Priolo A Sukhatme G. S. mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2015
Rivista:	IEEE TRANSACTIONS ON MOBILE COMPUTING
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

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11590/138981

Citazioni

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