AN OPTIMAL DISTRIBUTED ALGORITHM FOR RECOGNIZING MESH-CONNECTED NETWORKS

Authors
SUBBIAH R IYENGAR SS RADHAKRISHNAN S KASHYAP RL
Citation
R. Subbiah et al., AN OPTIMAL DISTRIBUTED ALGORITHM FOR RECOGNIZING MESH-CONNECTED NETWORKS, Theoretical computer science, 120(2), 1993, pp. 261-278
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
120
Issue
2
Year of publication
1993
Pages
261 - 278
Database
ISI
SICI code
0304-3975(1993)120:2<261:AODAFR>2.0.ZU;2-B
Abstract
In this paper, we consider the problem of recognizing whether a given network is a rectangular mesh. We present an efficient distributed alg orithm 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 algorit hm presented in Mohan (I 990) 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.