{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T01:45:42Z","timestamp":1768009542627,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662006","type":"print"},{"value":"9783540486862","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_36","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T15:54:12Z","timestamp":1184601252000},"page":"360-369","source":"Crossref","is-referenced-by-count":21,"title":["On Routing in Circulant Graphs"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"George","family":"Havas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernard","family":"Mans","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ajay","family":"Nerurkar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Pierre","family":"Seifert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Generating hard instances of lattice problems. In Proc. 28th Annual ACM Symposium on the Theory of Computing (1996) 99\u2013108.","DOI":"10.1145\/237814.237838"},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai. The shortest vector problem in L 2 is NP-hard for randomized reductions. In Proc. 30th Annual ACM Symposium on the Theory of Computing (1998) 10\u201319.","DOI":"10.1145\/276698.276705"},{"key":"36_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case\/average-case equivalence. In Proc. 29th ACM Symposium on Theory of Computing (1997) 284\u2013293.","DOI":"10.1145\/258533.258604"},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. In Proc. 34th IEEE Symposium on Foundations of Computer Science (FOCS), 724\u2013733, 1993.","DOI":"10.1109\/SFCS.1993.366815"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1006\/jpdc.1995.1002","volume":"24","author":"J.-C. Bermond","year":"1995","unstructured":"J.-C. Bermond, F. Comellas and D. F. Hsu. Distributed loop computer networks: A survey. Journal of Parallel and Distributed Computing 24 (1995) 2\u201310.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0304-3975(98)00058-9","volume":"207","author":"J.-Y. Cai","year":"1998","unstructured":"J-Y. Cai. A relation of primal-dual lattices and the complexity of shortest lattice vector problem. Theoretical Computer Science 207 (1998) 105\u2013116.","journal-title":"Theoretical Computer Science"},{"key":"36_CR7","unstructured":"J-Y. Cai and A. Nerurkar. An improved worst-case to average-case connection for lattice problems. In Proc. 38th IEEE Symposium on Foundations of Computer Science (1997) 468\u2013477."},{"key":"36_CR8","unstructured":"J-Y. Cai and A. Nerurkar. Approximating the SVP to within a factor $$ \\left( {1 + \\frac{1} {{\\dim ^ \\in }}} \\right) $$ is NP-hard under randomized reductions. In Proc. 13th Annual IEEE Conference on Computational Complexity (1998) 46\u201355."},{"key":"36_CR9","doi-asserted-by":"crossref","unstructured":"J. W. S. Cassels. An introduction to the geometry of numbers. Springer-Verlag, 1959.","DOI":"10.1007\/978-3-642-62035-5"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0020-0190(98)00099-4","volume":"67","author":"N. Chalamaiah","year":"1998","unstructured":"N. Chalamaiah and B. Ramamurty. Finding shortest paths in distributed loop networks. Inform. Proc. Letters 67 (1998) 157\u2013161.","journal-title":"Inform. Proc. Letters"},{"key":"36_CR11","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/0196-6774(88)90030-2","volume":"9","author":"Y. Cheng","year":"1988","unstructured":"Y. Cheng and F. K. Hwang. Diameters of weighted loop networks. J. of Algorithms 9 (1988) 401\u2013410.","journal-title":"J. of Algorithms"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1112\/blms\/26.2.140","volume":"26","author":"J. A. Dias da Silva","year":"1994","unstructured":"J. A. Dias da Silva and Y. O. Hamidoune. Cyclic spaces for Grassmann derivatives and additive theory Bull. Lond. Math. Soc. 26 (1994) 140\u2013146.","journal-title":"Bull. Lond. Math. Soc."},{"key":"36_CR13","unstructured":"I. Dinur, G. Kindler and S. Safra. Approximating-CVP to within almost-polynomial factors is NP-hard. 1998."},{"key":"36_CR14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.4064\/aa-9-2-149-159","volume":"9","author":"P. Erd\u00f6s","year":"1964","unstructured":"P. Erd\u00f6s and H. Heilbronn On the addition of residue classes mod p Acta Arithm. 9 (1964) 149\u2013159.","journal-title":"Acta Arithm."},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"O. Goldreich and S. Goldwasser. On the limits of non-approximability of lattice problems. In Proc. 30th Annual ACM Symposium on the Theory of Computing (1998) 1\u20139.","DOI":"10.1145\/276698.276704"},{"key":"36_CR16","unstructured":"O. Goldreich, S. Goldwasser and S. Halevi. Collision-free hashing from lattice problems. 1996. Available as TR96-042 from Electronic Colloquium on Computational Complexity at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"36_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BFb0052230","volume-title":"Advances in Cryptology \u2014 CRYPTO '97","author":"O. Goldreich","year":"1997","unstructured":"O. Goldreich, S. Goldwasser and S. Halevi. Eliminating decryption errors in the Ajtai-Dwork cryptosystem. Advances in Cryptology \u2014 CRYPTO '97 (editor B. Kaliski Jr.), Lecture Notes in Computer Science 1294 (Springer Verlag, 1997) 105\u2013111."},{"key":"36_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/BFb0052231","volume-title":"Advances in Cryptology \u2014 CRYPTO '97","author":"O. Goldreich","year":"1997","unstructured":"O. Goldreich, S. Goldwasser and S. Halevi. Public-key cryptosystems from lattice reduction problems. Advances in Cryptology \u2014 CRYPTO '97 (editor B. Kaliski Jr.), Lecture Notes in Computer Science 1294 (Springer Verlag, 1997) 112\u2013131."},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0020-0190(98)00013-1","volume":"65","author":"D. J. Guan","year":"1998","unstructured":"D. J. Guan. Finding shortest paths in distributed loop networks. Inform. Proc. Letters 65 (1998) 255\u2013260.","journal-title":"Inform. Proc. Letters"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"J. C. Lagarias. The computational complexity of simultaneous diophantine approximation problems. In Proc. 23rd IEEE Symposium on Foundations of Computer Science (1982) 32\u201339.","DOI":"10.1109\/SFCS.1982.43"},{"key":"36_CR21","doi-asserted-by":"crossref","unstructured":"F. T. Leighton. Introduction to parallel algorithms and architectures: Arrays, trees, hypercubes. M. Kaufmann, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"A. K. Lenstra","year":"1982","unstructured":"A. K. Lenstra, H. W. Lenstra and L. Lov\u00e1sz. Factoring polynomials with rational coefficients. Mathematische Annalen 261 (1982) 515\u2013534.","journal-title":"Mathematische Annalen"},{"key":"36_CR23","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jpdc.1997.1389","volume":"46","author":"B. Mans","year":"1997","unstructured":"B. Mans. Optimal Distributed algorithms in unlabeled tori and chordal rings. Journal on Parallel and Distributed Computing 46 (1997) 80\u201390.","journal-title":"Journal on Parallel and Distributed Computing"},{"key":"36_CR24","doi-asserted-by":"crossref","unstructured":"D. Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. In Proc. 39th IEEE Symposium on Foundations of Computer Science (1998) 92\u201398.","DOI":"10.1109\/SFCS.1998.743432"},{"key":"36_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-18088-5_33","volume-title":"Automata, Languages and Programming, 14th International Colloquium","author":"A. Paz","year":"1987","unstructured":"A. Paz and C. P. Schnorr. Approximating integer lattices by lattices with cyclic factor groups. Automata, Languages and Programming, 14th International Colloquium, Lecture Notes in Computer Science 267 (Springer-Verlag, 1987) 386\u2013393."},{"key":"36_CR26","unstructured":"R. Raz. Personal communication."},{"key":"36_CR27","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0304-3975(87)90064-8","volume":"53","author":"C. P. Schnorr","year":"1987","unstructured":"C. P. Schnorr. A hierarchy of polynomial time basis reduction algorithms. Theoretical Computer Science 53 (1987) 201\u2013224.","journal-title":"Theoretical Computer Science"},{"key":"36_CR28","unstructured":"J-P. Seifert and J. Bl\u00f6mer. On the complexity of computing short linearly independent vectors and short bases in a lattice. To appear in the proceedings of STOC 1999."},{"key":"36_CR29","unstructured":"P. van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in lattices. Technical Report 81-04, Mathematics Department, University of Amsterdam, 1981."},{"key":"36_CR30","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1006\/jagm.1993.1011","volume":"14","author":"J. \u017dervonik","year":"1993","unstructured":"J. \u017dervonik and T. Pisanski. Computing the diameter in multi-loop networks. J. of Algorithms 14 (1993) 226\u2013243.","journal-title":"J. of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:14:24Z","timestamp":1556680464000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}