Oriented Diameter of Grids

A grid is a large-scale geographically distributed hardware and software infrastructure composed of heterogeneous networked resources owned and shared by multiple administrative organizations which are coordinated to provide transparent, dependable, pervasive and consistent computing support to a wide range of applications. One of the major problems in graph theory is to find the oriented diameter of a graph $G$, which is defined as the smallest diameter among the diameter of all strongly connected orientations. The problem is proved to be NP-complete. In this paper, we obtain the oriented diameter of grids.