{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:28:52Z","timestamp":1787326132595,"version":"build-2736575974"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are as follows: A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in $O(\\log\\log N)$ communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.<\/jats:p>","DOI":"10.1137\/060669164","type":"journal-article","created":{"date-parts":[[2009,11,5]],"date-time":"2009-11-05T18:18:20Z","timestamp":1257445100000},"page":"1612-1645","source":"Crossref","is-referenced-by-count":0,"title":["On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks"],"prefix":"10.1137","volume":"23","author":[{"given":"Juraj","family":"Hromkovi\u010d","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Przemys\u0141awa","family":"Kanarek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ralf","family":"Klasing","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krzysztof","family":"Lory\u015b","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Walter","family":"Unger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hubert","family":"Wagener","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,11,5]]},"reference":[{"key":"R1","unstructured":"S. Bandyopadhyay,\n                      Dissemination of Information in Optical Networks: From Technology to Algorithms\n                      , In Cooperation with Ralf Klasing, Texts Theoret. Comput. Sci. EATCS Ser., Springer-Verlag, Berlin, 2008."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.077"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1964.tb04102.x"},{"key":"R4","unstructured":"V. Bene\u0161,\n                      Mathematical Theory of Connecting Networks and Telephone Traffic\n                      , Academic Press, New York, 1965."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1080\/00207169908804884"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798344847"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1109\/12.381954"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/71.780867"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/05062336X"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080308"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2004.08.001"},{"key":"R12","unstructured":"J. de Rumeur,\n                      Communications dans les R\u00e9seaux de Processeurs\n                      , Collection Etudes et Recherches en Informatique, Masson, Paris, 1994."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.007"},{"key":"R14","unstructured":"D.Z. Du and F. K. Hwang, eds.\n                      Advances in Switching Networks\n                      , DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 42, American Math Society, Providence, RI, 1997."},{"key":"R15","unstructured":"D.Z. Du and H. Q. Ngo, eds.\n                      Switching Networks: Recent Advances\n                      , Netw. Theory Appl. 5, Kluwer Academic Publishers, Dordrecht, 2001."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"R17","unstructured":"F. Harary,\n                      Graph Theory\n                      , Addison\u2013Wesley, Reading, MA, 1972."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180406"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, P. Kanarek, R. Klasing, K. Lory\u015b, W. Unger, and H. Wagener,\n                      On the sizes of permutation networks and consequences for efficient simulation of hypercube algorithms on bounded-degree networks\n                      , in Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science (STACS '95), Lecture Notes in Comput. Sci. 900, Springer-Verlag, Berlin, 1995, pp. 255\u2013266.","DOI":"10.1007\/3-540-59042-0_78"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d, R. Klasing, B. Monien, and R. Peine,\n                      Dissemination of information in interconnection networks (broadcasting and gossiping)\n                      , in Combinatorial Network Theory, D. Du and D. F. Hsu eds., Kluwer Academic Publishers, 1996, pp. 125\u2013212.","DOI":"10.1007\/978-1-4757-2491-2_5"},{"key":"R21","unstructured":"J. Hromkovi\u010d, R. Klasing, A. Pelc, P. Ru\u017ei\u010dka, and W. Unger,\n                      Dissemination of information in communication networks: Broadcasting, gossiping, leader election, and fault-tolerance\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer-Verlag, Berlin, 2005."},{"key":"R22","first-page":"295","volume":"15","author":"Hromkovi\u010d J.","year":"1996","journal-title":"Comput. Artificial Intelligence"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1154"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.2618"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. Kahn, G. Kalai, and N. Linial,\n                      The influence of variables on boolean functions (extended abstract)\n                      , in Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (FOCS '88), White Plains, NY, 1988, pp. 68\u201380.","DOI":"10.1109\/SFCS.1988.21923"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00112-1"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0405045"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"P. Kanarek and K. Lory\u015b,\n                      Periodic shifting networks\n                      , in Switching Networks: Recent Advances, D. Z. Du and H. Q. Ngo, eds., Kluwer Academic, Dordrecht, The Netherlands, 2001, pp. 191\u2013214.","DOI":"10.1007\/978-1-4613-0281-0_9"},{"key":"R29","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming, Volume 1: Fundamental Algorithms\n                      , 2nd ed., Addison\u2013Wesley, 1968, 1973."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"F. T. Leighton,\n                      Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes\n                      , Morgan Kaufmann, San Francisco, CA, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00579-0"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442714"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702408235"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00281-9"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1137\/0206022"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321962"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/358645.358660"},{"key":"R38","unstructured":"J. D. Ullman,\n                      Computational Aspects of VLSI\n                      , Computer Science Press, Rockville, MD, 1984."},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1145\/321439.321449"},{"key":"R40","unstructured":"R. Wanka,\n                      Paralleles Sortieren auf mehrdimensionalen Gittern\n                      . Ph.D. dissertation, Universit\u00e4t Paderborn, Paderborn, Germany, 1994."},{"key":"R41","unstructured":"R. Werchner,\n                      private communication\n                      , Fachbereich Mathematik\/Informatik,Johann Wolfgang Goethe-University at Frankfurt, Frankfurt, Germany, 1994."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"D. B. Wilson,\n                      Embedding leveled hypercube algorithms into hypercubes\n                      , in Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (SPAA '92), San Diego, CA, 1992, pp. 264\u2013270.","DOI":"10.1145\/140901.141881"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060669164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:27:11Z","timestamp":1787322431000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060669164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/060669164"],"URL":"https:\/\/doi.org\/10.1137\/060669164","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}