New edge sorting criterion for maximum clique search algorithm in unit disk graphs

Unit disk graphs (UDG) are a natural choice for wireless network modeling. However, complex UDG algorithms with a long processing time could be ineffective because of nodes mobility and the lack of processing power of the nodes. Therefore, they should be adapted for use in wireless networks. In this paper we present an accelerated algorithm for maximum clique in UDG using simple calculations. The input of the algorithm is an ordered set of graph edges. Our approach is to decrease the number of edges involved in algorithm, and then to reorder the edges for faster processing. The ordering criterion uses two-hop neighborhood information. The simulation results show a significant shortening of algorithm processing time. Two types of node distribution, x-y and p-φ were tested. The results depend on the distribution type. This indicates a possibility to create adaptive algorithms fitted to a specific type of node distribution in the network.