|
|||||
|
|
An optimal distributed algorithm for recognizing mesh-connected networks |
|
| Authors: | Rajanarayanan Subbiah and Sitharama S Iyengar Sridhar Radhakrishnan R L Kashyap |
| Affiliation: | Department of Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA School of Electrical Engineering and Computer Science, University of Oklahoma, Norman, OK 73019, USA Department of Electrical Engineering, Purdue University, West Lafayette, IN 47907, USA |
| Abstract: | In this paper, we consider the problem of recognizing whether a given network is a rectangular mesh. We present an efficient distributed algorithm with an O(N) message and time complexity, where N is the number of nodes in the network. This is an improvement of a previous algorithm presented in Mohan (1990) with a message complexity of O(N log N) and time complexity of O(N1.6). The proposed algorithm is constructive in nature and also assigns coordinates to the nodes of the network. |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ | |
