On routing in circulant graphs

We investigate various problems related to circulant graphs- finding the shortest path between two vertices, finding the shortest loop, and computing the diameter. These problems are related to short- est vector problems in a special class of lattices. We give matching upper and lower bounds on the length of the shortest loop. We claim NP- hardness results, and establish a worst-case/average-case connection for the shortest loop problem. A pseudo-polynomial time algorithm for these problems is also given. Our main tools are results and methods from the geometry of numbers