{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T07:08:12Z","timestamp":1774595292481,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T00:00:00Z","timestamp":1373500800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s00453-013-9810-3","type":"journal-article","created":{"date-parts":[[2013,7,10]],"date-time":"2013-07-10T15:43:52Z","timestamp":1373471032000},"page":"301-325","source":"Crossref","is-referenced-by-count":3,"title":["Random Walks, Bisections and Gossiping in Circulant Graphs"],"prefix":"10.1007","volume":"70","author":[{"given":"Bernard","family":"Mans","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Shparlinski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,7,11]]},"reference":[{"key":"9810_CR1","first-page":"393","volume":"3","author":"A. \u00c1d\u00e1m","year":"1967","unstructured":"\u00c1d\u00e1m, A.: Research problem 2\u201310. J. Comb. Theory 3, 393 (1967)","journal-title":"J. Comb. Theory"},{"key":"9810_CR2","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1017\/S0963548311000125","volume":"20","author":"N. Alon","year":"2011","unstructured":"Alon, N., Avin, C., Kouck, M., Kozma, G., Lotker, Z., Tuttle, M.R.: Many random walks are faster than one. Comb. Probab. Comput. 20, 481\u2013502 (2011)","journal-title":"Comb. Probab. Comput."},{"key":"9810_CR3","first-page":"59","volume-title":"Groups Complex. Crypto","author":"G. Amir","year":"2010","unstructured":"Amir, G., Gurel-Gurevich, O.: The diameter of a random Cayley graph of $\\mathbb{Z}_{q}$ . In: Groups Complex. Crypto, vol. 2, pp. 59\u201365 (2010)"},{"key":"9810_CR4","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF01371728","volume":"26","author":"F. Annexstein","year":"1993","unstructured":"Annexstein, F., Baumslag, M.: On the diameter and bisector size of Cayley graphs. Math. Syst. Theory 26, 271\u2013291 (1993)","journal-title":"Math. Syst. Theory"},{"key":"9810_CR5","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/BF01553900","volume":"4","author":"H. Attiya","year":"1989","unstructured":"Attiya, H., van Leeuwen, J., Santoro, N., Zaks, S.: Efficient elections in chordal ring networks. Algorithmica 4, 437\u2013446 (1989)","journal-title":"Algorithmica"},{"key":"9810_CR6","series-title":"LNCS","first-page":"162","volume-title":"Proc. 25th MFCS","author":"L. Barri\u00e8re","year":"2004","unstructured":"Barri\u00e8re, L., F\u00e0brega, J.: Edge-bisection of chordal rings. In: Proc. 25th MFCS. LNCS, pp. 162\u2013171. Springer, Berlin (2004)"},{"key":"9810_CR7","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0304-3975(00)00213-9","volume":"264","author":"L. Barri\u00e8re","year":"2001","unstructured":"Barri\u00e8re, L., Cohen, J., Mitjana, M.: Gossiping in chordal rings under the line model. Theor. Comput. Sci. 264, 53\u201364 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"9810_CR8","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jpdc.1995.1002","volume":"24","author":"J.-C. Bermond","year":"1995","unstructured":"Bermond, J.-C., Comellas, F., Hsu, D.F.: Distributed loop computer networks: a survey. J. Parallel Distrib. Comput. 24, 2\u201310 (1995)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9810_CR9","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/BF01301966","volume":"29","author":"S.R. Blackburn","year":"1996","unstructured":"Blackburn, S.R.: Node bisectors of Cayley graphs. Math. Syst. Theory 29, 589\u2013598 (1996)","journal-title":"Math. Syst. Theory"},{"key":"9810_CR10","series-title":"LNCS","first-page":"370","volume-title":"Proc. 5th COCOON","author":"J.-Y. Cai","year":"1999","unstructured":"Cai, J.-Y., Havas, G., Mans, B., Nerurkar, A., Seifert, J.-P., Shparlinski, I.: On routing in circulant graphs. In: Proc. 5th COCOON. LNCS, pp. 370\u2013378. Springer, Berlin (1999)"},{"key":"9810_CR11","first-page":"229","volume":"9","author":"B. Elspas","year":"1970","unstructured":"Elspas, B., Turner, J.: Graphs with circulant adjacency matrices. J. Comb. Theory 9, 229\u2013240 (1970)","journal-title":"J. Comb. Theory"},{"key":"9810_CR12","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01192695","volume":"29","author":"Y.O. Hamidoune","year":"1996","unstructured":"Hamidoune, Y.O., Serra, O.: On small cuts separating an Abelian Cayley graph into two equal parts. Math. Syst. Theory 29, 407\u2013409 (1996)","journal-title":"Math. Syst. Theory"},{"key":"9810_CR13","volume-title":"An Introduction to the Theory of Numbers","author":"G.H. Hardy","year":"1979","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Clarendon, New York (1979)","edition":"5"},{"key":"9810_CR14","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1006\/inco.1995.1154","volume":"123","author":"J. Hromkovi\u010d","year":"1995","unstructured":"Hromkovi\u010d, J., Klasing, R., St\u00f6hr, E.A., Wagener, H.: Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs. Inf. Comput. 123, 17\u201328 (1995)","journal-title":"Inf. Comput."},{"key":"9810_CR15","first-page":"295","volume":"15","author":"J. Hromkovi\u010d","year":"1996","unstructured":"Hromkovi\u010d, J., Klasing, R., St\u00f6hr, E.A.: Dissemination of information in generalized communication modes. Comput. Artif. Intell. 15, 295\u2013318 (1996)","journal-title":"Comput. Artif. Intell."},{"key":"9810_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/inco.1996.2618","volume":"133","author":"J. Hromkovi\u010d","year":"1997","unstructured":"Hromkovi\u010d, J., Klasing, R., Unger, W., Wagener, H.: Optimal algorithms for broadcast and gossip in the edge-disjoint path modes. Inf. Comput. 133, 1\u201333 (1997)","journal-title":"Inf. Comput."},{"key":"9810_CR17","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/053","volume-title":"Analytic Number Theory","author":"H. Iwaniec","year":"2004","unstructured":"Iwaniec, H., Kowalski, E.: Analytic Number Theory. Am. Math. Soc., Providence (2004)"},{"key":"9810_CR18","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0166-218X(97)00112-1","volume":"83","author":"R. Klasing","year":"1998","unstructured":"Klasing, R.: The relationship between the gossip complexity in the vertex-disjoint paths mode and the vertex bisection width. Discrete Appl. Math. 83, 229\u2013246 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9810_CR19","first-page":"105","volume":"30","author":"M. Laczkovich","year":"1995","unstructured":"Laczkovich, M.: Discrepancy estimates for sets with small boundary. Studia Sci. Math. Hung. 30, 105\u2013109 (1995)","journal-title":"Studia Sci. Math. Hung."},{"key":"9810_CR20","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo (1992)"},{"key":"9810_CR21","series-title":"Combinatorics, Paul Erd\u00f6s Is Eighty","first-page":"1","volume-title":"Random Walks on Graphs: a Survey","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L.: Random Walks on Graphs: a Survey. Combinatorics, Paul Erd\u00f6s Is Eighty, pp. 1\u201346. Bolyai Soc., Hungary (1993)"},{"key":"9810_CR22","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1006\/jpdc.1997.1389","volume":"46","author":"B. Mans","year":"1997","unstructured":"Mans, B.: Optimal distributed algorithms in unlabeled tori and chordal rings. J. Parallel Distrib. Comput. 46, 80\u201390 (1997)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9810_CR23","series-title":"LNCS","first-page":"589","volume-title":"Proc. 6th LATIN","author":"B. Mans","year":"2004","unstructured":"Mans, B., Shparlinski, I.E.: Bisecting and gossiping in circulant graphs. In: Proc. 6th LATIN. LNCS, pp. 589\u2013598. Springer, Berlin (2004)"},{"key":"9810_CR24","series-title":"LNCS","first-page":"542","volume-title":"Proc. 10th LATIN","author":"B. Mans","year":"2012","unstructured":"Mans, B., Shparlinski, I.E.: Random walks and bisections in random circulant graphs. In: Proc. 10th LATIN. LNCS, pp. 542\u2013555. Springer, Berlin (2012)"},{"key":"9810_CR25","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/S0012-365X(01)00374-0","volume":"254","author":"B. Mans","year":"2002","unstructured":"Mans, B., Pappalardi, F., Shparlinski, I.: On the spectral \u00c1d\u00e1m property for circulant graphs. Discrete Math. 254, 309\u2013329 (2002)","journal-title":"Discrete Math."},{"key":"9810_CR26","unstructured":"Marklof, J., Strombergsson, A.: Diameters of random circulant graphs. Combinatorica. Available from: http:\/\/arxiv.org\/abs\/1103.3152 (2011, to appear)"},{"key":"9810_CR27","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1016\/S0012-365X(96)00251-8","volume":"167\/168","author":"M. Muzychuk","year":"1997","unstructured":"Muzychuk, M.: On \u00c1d\u00e1m\u2019s conjecture for circulant graphs. Discrete Math. 167\/168, 497\u2013510 (1997). Erratum: Discrete Math. 176, 285\u2013298 (1997)","journal-title":"Discrete Math."},{"key":"9810_CR28","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1007\/s004530010067","volume":"29","author":"L. Narayanan","year":"2001","unstructured":"Narayanan, L., Opatrny, J., Sotteau, D.: All-to-all optical routing in optimal chordal rings of degree 4. Algorithmica 29, 396\u2013409 (2001)","journal-title":"Algorithmica"},{"key":"9810_CR29","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF01190941","volume":"144","author":"H. Niederreiter","year":"1975","unstructured":"Niederreiter, H., Wills, J.M.: Diskrepanz und Distanz von Massen bezuglich konvexer und Jordanscher Mengen. Math. Z. 144, 125\u2013134 (1975)","journal-title":"Math. Z."},{"issue":"1\u20133","key":"9810_CR30","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0304-3975(02)00649-7","volume":"297","author":"J. Opatrny","year":"2003","unstructured":"Opatrny, J.: Uniform multi-hop all-to-all optical routings in rings. Theor. Comput. Sci. 297(1\u20133), 385\u2013397 (2003)","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9810-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9810-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9810-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:12Z","timestamp":1559123112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9810-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,11]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["9810"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9810-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,11]]}}}