On routing in circulant graphs

Jin Yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean Pierre Seifert, Igor Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

25 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings
EditorsTakano Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, Takeshi Tokuyama
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages360-369
Number of pages10
ISBN (Electronic)9783540486862
ISBN (Print)3540662006, 9783540662006
DOIs
Publication statusPublished - Jul 1999
Event5th Annual International Conference on Computing and Combinatorics, COCOON - 1999 - Tokyo, Japan
Duration: 26 Jul 199928 Jul 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1627
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other5th Annual International Conference on Computing and Combinatorics, COCOON - 1999
CountryJapan
CityTokyo
Period26/07/9928/07/99

Keywords

  • Circulant graphs
  • Diameter
  • Lattices
  • Loops
  • Shortest paths

Fingerprint Dive into the research topics of 'On routing in circulant graphs'. Together they form a unique fingerprint.

Cite this