Embedding linear arrays of the maximum length in O-shaped meshes.

Embedding an interconnection network into another network is one of the important problems in parallel processing. In this paper, we study embedding of linear arrays (paths) of maximum length in O-shaped meshes (O-shaped grid graphs). This is equal to finding a longest path in an O-shaped mesh (grid graph). An O-shaped mesh is a 2D mesh that a smaller 2D mesh is removed from it. The removed nodes can be considered as faulty processor. We give a linear-time parallel algorithm for this problem. To show the algorithm finds an optimal path, first we prove some upper bounds on the length of the longest paths, then we show that how our algorithm meets these upper bounds. [ABSTRACT FROM AUTHOR]