@inproceedings{e95abd37676e4994be1b89019f4693f1,
title = "On routing in circulant graphs",
abstract = "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.",
keywords = "Circulant graphs, Diameter, Lattices, Loops, Shortest paths",
author = "Cai, {Jin Yi} and George Havas and Bernard Mans and Ajay Nerurkar and Seifert, {Jean Pierre} and Igor Shparlinski",
year = "1999",
month = jul,
doi = "10.1007/3-540-48686-0_36",
language = "English",
isbn = "3540662006",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer, Springer Nature",
pages = "360--369",
editor = "Takano Asano and Hideki Imai and Lee, {D. T.} and Shin-ichi Nakano and Takeshi Tokuyama",
booktitle = "Computing and Combinatorics",
address = "United States",
note = "5th Annual International Conference on Computing and Combinatorics, COCOON - 1999 ; Conference date: 26-07-1999 Through 28-07-1999",
}