On routing in circulant graphs

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

doi:10.1007/3-540-48686-0_36

On routing in circulant graphs

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

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings
Editors	Takano Asano, Hideki Imai, D. T. Lee, Shin-ichi Nakano, Takeshi Tokuyama
Place of Publication	Berlin; New York
Publisher	Springer, Springer Nature
Pages	360-369
Number of pages	10
ISBN (Electronic)	9783540486862
ISBN (Print)	3540662006, 9783540662006
DOIs	https://doi.org/10.1007/3-540-48686-0_36
Publication status	Published - Jul 1999
Event	5th Annual International Conference on Computing and Combinatorics, COCOON - 1999 - Tokyo, Japan Duration: 26 Jul 1999 → 28 Jul 1999

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1627
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	5th Annual International Conference on Computing and Combinatorics, COCOON - 1999
Country	Japan
City	Tokyo
Period	26/07/99 → 28/07/99

Keywords

Circulant graphs
Diameter
Lattices
Loops
Shortest paths

Access to Document

10.1007/3-540-48686-0_36

Link to publication in Scopus

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

Cite this

Cai, J. Y., Havas, G., Mans, B., Nerurkar, A., Seifert, J. P., & Shparlinski, I. (1999). On routing in circulant graphs. In T. Asano, H. Imai, D. T. Lee, S. Nakano, & T. Tokuyama (Eds.), Computing and Combinatorics: 5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings (pp. 360-369). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1627). Berlin; New York: Springer, Springer Nature. https://doi.org/10.1007/3-540-48686-0_36

Cai, Jin Yi ; Havas, George ; Mans, Bernard ; Nerurkar, Ajay ; Seifert, Jean Pierre ; Shparlinski, Igor. / On routing in circulant graphs. Computing and Combinatorics: 5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings. editor / Takano Asano ; Hideki Imai ; D. T. Lee ; Shin-ichi Nakano ; Takeshi Tokuyama. Berlin; New York : Springer, Springer Nature, 1999. pp. 360-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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 = "7",

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",

}

Cai, JY, Havas, G, Mans, B, Nerurkar, A, Seifert, JP & Shparlinski, I 1999, On routing in circulant graphs. in T Asano, H Imai, DT Lee, S Nakano & T Tokuyama (eds), Computing and Combinatorics: 5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1627, Springer, Springer Nature, Berlin; New York, pp. 360-369, 5th Annual International Conference on Computing and Combinatorics, COCOON - 1999, Tokyo, Japan, 26/07/99. https://doi.org/10.1007/3-540-48686-0_36

On routing in circulant graphs. / Cai, Jin Yi; Havas, George; Mans, Bernard; Nerurkar, Ajay; Seifert, Jean Pierre; Shparlinski, Igor.

Computing and Combinatorics: 5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings. ed. / Takano Asano; Hideki Imai; D. T. Lee; Shin-ichi Nakano; Takeshi Tokuyama. Berlin; New York : Springer, Springer Nature, 1999. p. 360-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1627).

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

TY - GEN

T1 - On routing in circulant graphs

AU - Cai, Jin Yi

AU - Havas, George

AU - Mans, Bernard

AU - Nerurkar, Ajay

AU - Seifert, Jean Pierre

AU - Shparlinski, Igor

PY - 1999/7

Y1 - 1999/7

N2 - 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.

AB - 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.

KW - Circulant graphs

KW - Diameter

KW - Lattices

KW - Loops

KW - Shortest paths

UR - http://www.scopus.com/inward/record.url?scp=48049110260&partnerID=8YFLogxK

U2 - 10.1007/3-540-48686-0_36

DO - 10.1007/3-540-48686-0_36

M3 - Conference proceeding contribution

SN - 3540662006

SN - 9783540662006

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 360

EP - 369

BT - Computing and Combinatorics

A2 - Asano, Takano

A2 - Imai, Hideki

A2 - Lee, D. T.

A2 - Nakano, Shin-ichi

A2 - Tokuyama, Takeshi

PB - Springer, Springer Nature

CY - Berlin; New York

ER -

Cai JY, Havas G, Mans B, Nerurkar A, Seifert JP, Shparlinski I. On routing in circulant graphs. In Asano T, Imai H, Lee DT, Nakano S, Tokuyama T, editors, Computing and Combinatorics: 5th Annual International Conference, COCOON’99 Tokyo, Japan, July 26–28, 1999 Proceedings. Berlin; New York: Springer, Springer Nature. 1999. p. 360-369. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-48686-0_36