AHSWN Home • Issue Contents • Forthcoming Papers
Efficient Algorithms on Rigidity Decomposition for Network Localizability Analysis
Xiaoping Wang, Lili Zhang and Kai Lu
Recent research shows that rigidity theory sets a theoretical basis for the distributed localization problem in wireless networks. Specifically, rigidity theory gives insights to many fundamental problems of localization, thus it is an essential tool for network analysis. However, there are two problems in current rigidity test algorithms: they can only provide binary result for rigidity; they suffer high computational complexity. We propose a set of high-efficiency rigidity and redundant rigidity determination and decomposition algorithms, and the time complexities of all algorithms are proven to be O(n2), where n is the number of vertices. The costs are optimal in graph processing. The experimental results show that these algorithms can efficiently solve the rigidity and redundant rigidity determination and decomposition problem, which is an effective tool set for network analysis.
Keywords: Rigidity theory, network localization, rigidity determination, rigidity decomposition, redundant rigidity decomposition, pebble game algorithm