{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T22:49:41Z","timestamp":1776466181424,"version":"3.51.2"},"reference-count":144,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6894,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1016\/0166-218x(94)90180-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T23:43:01Z","timestamp":1027640581000},"page":"79-133","source":"Crossref","is-referenced-by-count":285,"title":["Methods and problems of communication in usual networks"],"prefix":"10.1016","volume":"53","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]},{"given":"Emmanuel","family":"Lazard","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0166-218X(94)90180-5_BIB1","first-page":"393","article-title":"The star graph: an attractive alternative to the n-cube","author":"Akers","year":"1987","journal-title":"Proceedings of the International Conference on Parallel Processing"},{"key":"10.1016\/0166-218X(94)90180-5_BIB2","series-title":"Cycles and Rays","first-page":"9","article-title":"Decomposition into cycles 1: Hamilton decompositions","author":"Alspach","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB3","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0012-365X(82)90163-7","article-title":"D\u00e9composition de la somme cart\u00e9sienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens","volume":"38","author":"Aubert","year":"1982","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB4","series-title":"Tech. Rept. MIT\/LCS\/TM-365","article-title":"A tradeoff between information and communication in broadcast protocols","author":"Awerbuch","year":"1988"},{"key":"10.1016\/0166-218X(94)90180-5_BIB5","series-title":"Tech. Rept. CS-LPCR 9302","article-title":"On greedy hot-potatoe routing","author":"Ben-Dor","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB6","doi-asserted-by":"crossref","DOI":"10.1109\/12.204799","article-title":"Gossiping in a distributed network","volume":"42","author":"Bagchi","year":"1993","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB7","doi-asserted-by":"crossref","DOI":"10.1109\/12.256452","article-title":"Data transfers in broadcast networks","volume":"41","author":"Bagchi","year":"1992","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB8","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1137\/0222055","article-title":"Multiple communication in multihop radio networks","volume":"22","author":"Ber-Yehuda","year":"1993","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB9","series-title":"Graphes","author":"Berge","year":"1983"},{"key":"10.1016\/0166-218X(94)90180-5_BIB10","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/0743-7315(86)90008-0","article-title":"Strategies for interconnection networks: some methods from graph theory","volume":"3","author":"Bermond","year":"1986","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB11","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539791197852","article-title":"Broadcasting and gossiping in de Bruijn networks","volume":"23","author":"Bermond","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB12","article-title":"Communications in interconnection networks","author":"Bermond","year":"1991","journal-title":"Proceedings Combinatorial Optimization in Science and Technology '91"},{"key":"10.1016\/0166-218X(94)90180-5_BIB13","first-page":"8","article-title":"Broadcasting and NP-completeness","volume":"XXII","author":"Bermond","year":"1992","journal-title":"Graph Theory Notes of New York"},{"key":"10.1016\/0166-218X(94)90180-5_BIB14","series-title":"Tech. Rept. CMPT TR 92-03","article-title":"Antepenultimate broadcasting","author":"Bermond","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB15","series-title":"Chromatic index of the Kautz and the de Bruijn digraphs","author":"Bermond","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB16","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1137\/0405002","article-title":"Broadcasting in bounded degree graphs","volume":"5","author":"Bermond","year":"1992","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB17","series-title":"Second International Workshop on Distributed Algorithms","first-page":"41","article-title":"General and efficient decentralised consensus protocols","volume":"312","author":"Bermond","year":"1988"},{"key":"10.1016\/0166-218X(94)90180-5_BIB18","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/0167-8191(92)90004-Q","article-title":"Broadcasting on wraparound meshes with parallel monodirectional links","volume":"18","author":"Bermond","year":"1992","journal-title":"Parallel Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB19","series-title":"Hypercube and Distributed Computers","first-page":"279","article-title":"de Bruijn and Kautz networks: a competitor for the hypercube?","author":"Bermond","year":"1989"},{"key":"10.1016\/0166-218X(94)90180-5_BIB20","first-page":"283","article-title":"Broadcasting in de Bruijn networks","volume":"66","author":"Bermond","year":"1988","journal-title":"FL Congressus Numerantium"},{"key":"10.1016\/0166-218X(94)90180-5_BIB21","series-title":"LIP","author":"Berthom\u00e9","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB22","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0743-7315(91)90033-6","article-title":"Optimal communication algorithms for hypercube","volume":"11","author":"Bertsekas","year":"1991","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB23","series-title":"Tech. Rept. 93-18","article-title":"On bufferless routing of variable length messages in leveled networks","author":"Bhatt","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB24","doi-asserted-by":"crossref","first-page":"938","DOI":"10.1109\/12.238484","article-title":"Scattering and gathering messages in networks of processors","volume":"42","author":"Bhatt","year":"1993","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB25","doi-asserted-by":"crossref","first-page":"1526","DOI":"10.1109\/12.42122","article-title":"Scan as a primitive parallel operation","volume":"38","author":"Blelloch","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB26","series-title":"Hypercube and Distributed Computers","first-page":"311","article-title":"Communication benchmarks for the iPSC\/2","author":"Bomans","year":"1989"},{"key":"10.1016\/0166-218X(94)90180-5_BIB27","series-title":"Tech. Rept. RJ 8763","article-title":"Multiple message broadcasting with generalized fibonacci trees","author":"Bruck","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB28","first-page":"19","article-title":"Time bounds for broadcasting in bounded degree graphs","author":"Capocelli","year":"1989","journal-title":"WG 89: 15th International Workshop on Graphtheoretic Concepts in Computer Science"},{"key":"10.1016\/0166-218X(94)90180-5_BIB29","series-title":"LIP-IMAG 89-02","article-title":"Tnode: document utilisateur","author":"Champion","year":"1989"},{"key":"10.1016\/0166-218X(94)90180-5_BIB30","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0167-8191(90)90032-5","article-title":"Finding the roots of a polynomial on an MIMD multicomputer","volume":"15","author":"Cosnard","year":"1990","journal-title":"Parallel Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB31","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0221010","article-title":"Gossiping in minimum time","volume":"21","author":"Cybenko","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB32","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1109\/12.53599","article-title":"Performance analysis of k-ray n-cube interconnection networks","volume":"39","author":"Dally","year":"1990","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB33","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1109\/TC.1987.1676939","article-title":"Deadlock-free message routing in multiprocessor interconnection networks","volume":"36","author":"Dally","year":"1987","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB34","unstructured":"E. Darrot, Manuscript."},{"key":"10.1016\/0166-218X(94)90180-5_BIB35","series-title":"PhD Thesis","article-title":"Etudes de certains r\u00e9seaux d'interconnexion: structures et communications","author":"Djelloul","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB36","doi-asserted-by":"crossref","first-page":"1320","DOI":"10.1109\/71.250114","article-title":"A new theory of deadlock-free adaptive routing in wormhole networks","volume":"4","author":"Duato","year":"1993","journal-title":"IEEE Trans. Parallel Distrib. Systems"},{"key":"10.1016\/0166-218X(94)90180-5_BIB37","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/0743-7315(91)90039-C","article-title":"Optimal matrix transposition and bit reversal on hypercubes: All to all personalized communication","volume":"11","author":"Edelman","year":"1991","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB38","series-title":"Combinatorial Algorithms","first-page":"91","article-title":"Edges-disjoint branchings, combinatorial algorithms","author":"Edmonds","year":"1972"},{"key":"10.1016\/0166-218X(94)90180-5_BIB39","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/0016-0032(79)90004-8","article-title":"Gossips and telegraphs","volume":"307","author":"Entringer","year":"1979","journal-title":"J. Franklin Inst."},{"key":"10.1016\/0166-218X(94)90180-5_BIB40","article-title":"On the number of rounds necessary to disseminate information","author":"Even","year":"1989","journal-title":"ACM Symposium on Parallel Algorithms and Architectures"},{"key":"10.1016\/0166-218X(94)90180-5_BIB41","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/BF01994840","article-title":"Optimal algorithms for total exchange without buffering on the hypercube","volume":"32","author":"Fack","year":"1992","journal-title":"BIT"},{"key":"10.1016\/0166-218X(94)90180-5_BIB42","first-page":"161","article-title":"Gossiping in grid graphs","volume":"5","author":"Farley","year":"1980","journal-title":"J. Combin. Inform. Systems Sci."},{"key":"10.1016\/0166-218X(94)90180-5_BIB43","series-title":"Tech. Rept. CIS-TR-89-06","article-title":"Broadcasting: Between whispering and shouting","author":"Farley","year":"1989"},{"key":"10.1016\/0166-218X(94)90180-5_BIB44","series-title":"Tech. Rept. CIS-TR-91-22","article-title":"Bounded-call broadcasting","author":"Farley","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB45","first-page":"275","article-title":"Broadcasting in grid graphs","volume":"XXI","author":"Farley","year":"1978","journal-title":"FL Congressus Numerantium"},{"key":"10.1016\/0166-218X(94)90180-5_BIB46","series-title":"Res. Rept. 94-09","article-title":"Deadlocks in adaptive wormhole routing","author":"Fleury","year":"1994"},{"key":"10.1016\/0166-218X(94)90180-5_BIB47","series-title":"Res. Rept. 94-07","article-title":"Stategies for multicasting in meshes","author":"Fleury","year":"1994"},{"key":"10.1016\/0166-218X(94)90180-5_BIB48","series-title":"Tech. Rept. 93\u2013346","article-title":"Optimal communication algorithms on star graphs using spanning tree constructions","author":"Fragopoulou","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB49","series-title":"PhD Thesis","article-title":"Communications intensives dans les architectures \u00e0 m\u00e9moire distribu\u00e9e et algorithmes parall\u00e8les de recherche de racines de polyn\u00f4mes","author":"Fraigniaud","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB50","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0743-7315(92)90040-T","article-title":"Performance analysis of broadcasting in hypercubes with restricted communication capabilities","volume":"16","author":"Fraigniaud","year":"1992","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB51","series-title":"Res. Rept. 94-04","article-title":"Interval routing schemes","author":"Fraigniaud","year":"1994"},{"key":"10.1016\/0166-218X(94)90180-5_BIB52","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1142\/S012962649300006X","article-title":"Scheduling a scattering gathering sequence on hypercubes","volume":"3","author":"Fraigniaud","year":"1993","journal-title":"Parallel Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB53","first-page":"I225","article-title":"Arc-disjoint spanning trees on cube connected cycles networks","author":"Fraigniaud","year":"1991","journal-title":"Proceedings of International Conference on Parallel Processing"},{"key":"10.1016\/0166-218X(94)90180-5_BIB54","unstructured":"P. Fraigniaud and C. Laforest, Disjoint spanning trees of small depth, in: Proceedings of ParCo '93, to appear."},{"key":"10.1016\/0166-218X(94)90180-5_BIB55","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0167-8191(90)90140-5","article-title":"Scattering on a ring of processors","volume":"13","author":"Fraigniaud","year":"1990","journal-title":"Parallel Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB56","series-title":"Optimal gossip graphs","author":"Fraigniaud","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB57","series-title":"Structured communication in torus networks","author":"Fraigniaud","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB58","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0020-0190(93)90254-7","article-title":"Fast gossiping on square mesh computer","volume":"48","author":"Fujita","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB59","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0166-218X(94)90183-X","article-title":"Broadcasting on recursively decomposable Cayley graphs","volume":"53","author":"GowriSankaran","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB60","series-title":"Tech. Rept. 5\/94","article-title":"Multicomputer routing","author":"Grammatikakis","year":"1994"},{"key":"10.1016\/0166-218X(94)90180-5_BIB61","doi-asserted-by":"crossref","DOI":"10.1109\/12.277296","article-title":"The cost of broadcasting on Star graphs and k-ary hypercubes","volume":"42","author":"Graham","year":"1993","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB62","doi-asserted-by":"crossref","first-page":"447","DOI":"10.4153\/CMB-1972-081-0","article-title":"A cure for the telephone disease","volume":"18","author":"Hajnal","year":"1972","journal-title":"Canad. Math. Bull."},{"key":"10.1016\/0166-218X(94)90180-5_BIB63","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1002\/net.3230180406","article-title":"A survey of gossiping and broadcasting in communication networks","volume":"18","author":"Hedetniemi","year":"1986","journal-title":"Networks"},{"key":"10.1016\/0166-218X(94)90180-5_BIB64","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0166-218X(92)90141-V","article-title":"Broadcasting and spanning trees in de Bruijn and Kautz networks","volume":"37\/38","author":"Heydemann","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB65","series-title":"The Connection Machine","author":"Hillis","year":"1985"},{"key":"10.1016\/0166-218X(94)90180-5_BIB66","series-title":"Algorithmes d\u00e9change d'information dans les r\u00e9seaux \u00e0 bus","author":"Hily","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB67","first-page":"I276","article-title":"Full bandwidth communications on folded hypercubes","author":"Ho","year":"1990","journal-title":"Proceedings International Conference on Parallel Processing"},{"key":"10.1016\/0166-218X(94)90180-5_BIB68","series-title":"PhD Thesis","article-title":"Optimal communication primitives and graphs embeddings on hypercubes","author":"Ho","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB69","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/0743-7315(91)90094-P","article-title":"Optimal broadcasting on SIMD hypercubes without indirect addressing capability","volume":"13","author":"Ho","year":"1991","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB70","series-title":"Tech. Rept. YALEU\/DCS\/TR-508","article-title":"Spanning balanced trees in boolean cubes","author":"Ho","year":"1987"},{"key":"10.1016\/0166-218X(94)90180-5_BIB71","series-title":"Res. Rept. RJ 9385 (82637)","article-title":"Matrix transpose on meshes with wormhole and X Y routing","author":"Ho","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB72","series-title":"Res. Rept. RJ 9394 (82646)","article-title":"Optimal broadcast on hypercubes with wormhole and E-cube routing","author":"Ho","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB73","series-title":"Tech. Rept. RJ (72915)","article-title":"Efficient communication primitives on hypercubes","author":"Ho","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB74","series-title":"Tech. Rept. no. 71","article-title":"Optimal algorithms for dissemination of information in some interconnection networks","author":"Hromkovic","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB75","series-title":"Dissemination of information in interconnection networks (broadcasting and gossiping)","author":"Hromkovic","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB76","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Johnson","year":"1979"},{"key":"10.1016\/0166-218X(94)90180-5_BIB77","doi-asserted-by":"crossref","first-page":"1249","DOI":"10.1109\/12.29465","article-title":"Optimum broadcasting and personalized communication in hypercubes","volume":"38","author":"Johnsson","year":"1989","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB78","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0166-218X(94)90184-8","article-title":"Broadcasting in butterfly and deBruijn networks","volume":"53","author":"Klasing","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB79","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0012-365X(75)90090-4","article-title":"New gossips and telephones","volume":"13","author":"Knodel","year":"1975","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB80","first-page":"17","article-title":"Sequential generation of arrangements by mean of a basis of transpositions","volume":"3","author":"Kompel'makher","year":"1975","journal-title":"Kibernetica"},{"key":"10.1016\/0166-218X(94)90180-5_BIB81","unstructured":"J.C. Konig, D.W. Krumme and E. Lazard, Oriented torus diameter, Networks, to appear."},{"key":"10.1016\/0166-218X(94)90180-5_BIB82","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0166-218X(94)90185-6","article-title":"Minimum k-broadcast graphs","volume":"53","author":"K\u00f6nig","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB83","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1137\/0221026","article-title":"Fast gossiping for the hypercube","volume":"21","author":"Krumme","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB84","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0095-8956(74)90087-2","article-title":"Bounds on the number of disjoint spanning trees","volume":"17","author":"Kundu","year":"1974","journal-title":"J. Combin. Theory"},{"key":"10.1016\/0166-218X(94)90180-5_BIB85","first-page":"23","article-title":"Evaluating the performances of transputer based hypercube vector computer","volume":"4","author":"Kuppuswami","year":"1990","journal-title":"La Lettre Transput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB86","series-title":"Tech. Rept. 91708-OR","article-title":"Some minimum gossip graphs","author":"Labahn","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB87","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0012-365X(93)90509-R","article-title":"Information flows on hypergraphs","volume":"113","author":"Labhan","year":"1993","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB88","series-title":"Tech. Rept. 91707-OR","article-title":"Characterizing minimum gossip graphs on 16 vertices","author":"Labahn","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB89","doi-asserted-by":"crossref","unstructured":"R. Labahn and I. Warnke, Quick gossiping by telegraphs, Discrete Math., to appear.","DOI":"10.1016\/0012-365X(94)90290-9"},{"key":"10.1016\/0166-218X(94)90180-5_BIB90","series-title":"Topics in Combinatorics and Graph Theory","first-page":"451","article-title":"Quick gossiping by multi-telegraphs","author":"Labahn","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB91","series-title":"Master's thesis","article-title":"Arbres de recouvrement arc-disjoints de hauteur minimum","author":"Laforest","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB92","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/0743-7315(90)90066-X","article-title":"Multicast in hypercube multiprocessors","volume":"8","author":"Lan","year":"1990","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB93","first-page":"180","article-title":"On folded hypercubes","author":"Latifi","year":"1989","journal-title":"1989 International Conference on Parallel Processing I"},{"key":"10.1016\/0166-218X(94)90180-5_BIB94","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/0166-218X(92)90147-3","article-title":"Broadcasting in DMA-bound bounded degree graphs","volume":"37\/38","author":"Lazard","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB95","series-title":"Introduction to Parallel Algorithms and Architectures: Array, Trees, Hypercubes","author":"Leighton","year":"1992"},{"key":"10.1016\/0166-218X(94)90180-5_BIB96","series-title":"Tech. Rept. 91-03, LIP","article-title":"Multiscattering on a reconfigurable network of processors","author":"Li","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB97","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1137\/0401049","article-title":"Broadcast networks of bounded degrees","volume":"1","author":"Liestman","year":"1988","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB98","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1016\/0166-218X(92)90148-4","article-title":"Minimum broadcast digraphs","volume":"37\/38","author":"Liestman","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB99","doi-asserted-by":"crossref","DOI":"10.1109\/71.219758","article-title":"Network communication in edge-colored graphs: gossiping","volume":"4","author":"Liestman","year":"1993","journal-title":"IEEE Trans. Parallel Distrib. Systems"},{"key":"10.1016\/0166-218X(94)90180-5_BIB100","doi-asserted-by":"crossref","unstructured":"A. Liestman and D. Richards, Perpetual gossiping, Parallel Process. Lett., to appear.","DOI":"10.1142\/S0129626493000381"},{"key":"10.1016\/0166-218X(94)90180-5_BIB101","first-page":"633","article-title":"On the furthest-distance-first principle for data scattering with set-up","author":"Lyuu","year":"1993","journal-title":"Proceedings of the 5th IEEE Symposium on Parallel and Distributed Processing"},{"key":"10.1016\/0166-218X(94)90180-5_BIB102","doi-asserted-by":"crossref","unstructured":"Ph. MacKenzie, A lower bound for order preserving broadcast in the postal model, Parallel Process. Lett., to appear.","DOI":"10.1142\/S0129626493000356"},{"key":"10.1016\/0166-218X(94)90180-5_BIB103","series-title":"Tech. Rept. CS-TR-89-01","article-title":"Broadcasting on three multiprocessor interconnection topologies","author":"MacKenzie","year":"1989"},{"key":"10.1016\/0166-218X(94)90180-5_BIB104","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(94)90191-0","article-title":"Note on the problem of gossiping in multidimensional grids","volume":"53","author":"Mah\u00e9o","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB105","series-title":"Distributed Memory Computing","first-page":"7","article-title":"The next generation transputers and beyond","volume":"487","author":"May","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB106","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(88)90123-9","article-title":"Orientations of the n-cube with minimum diameter","volume":"68","author":"McCanna","year":"1988","journal-title":"Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB107","first-page":"I579","article-title":"Communication aspects of the cube-connected cycles","author":"Meliksetian","year":"1990","journal-title":"Proceedings of the International Conference on Parallel Processing"},{"key":"10.1016\/0166-218X(94)90180-5_BIB108","series-title":"Optimal routing algorithm and other communication issues of the cube-connected cycles","author":"Meliksetian","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB109","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1109\/71.149958","article-title":"Optimal broadcasting on the star graph","volume":"3","author":"Mendia","year":"1992","journal-title":"IEEE Trans. Parallel Distrib. Systems"},{"key":"10.1016\/0166-218X(94)90180-5_BIB110","article-title":"Optimal broadcasting algorithms on torus","author":"Michallon","year":"1992","journal-title":"RR 872-I-01-92 LMC-IMAG"},{"key":"10.1016\/0166-218X(94)90180-5_BIB111","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(93)90066-I","article-title":"Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2","volume":"46","author":"Middendorf","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB112","series-title":"PhD Thesis","article-title":"Programmation dynamique et traitement d'images sur machines parall\u00e8les a m\u00e9moire distribu\u00e9e","author":"Miguet","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB113","series-title":"Proceedings Journ\u00e9e Th\u00e9matique sur la Conception et la Programmation des Machines Parall\u00e8les","article-title":"Architectures parall\u00e8les pour l'ex\u00e9cution d'algorithmes de la vision","author":"Missakian","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB114","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1109\/TC.1981.6312172","article-title":"Data broadcasting in SIMD computers","volume":"30","author":"Nassimi","year":"1981","journal-title":"IEEE Trans. Comput."},{"issue":"26","key":"10.1016\/0166-218X(94)90180-5_BIB115","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/2.191995","article-title":"A survey of wormhole routing techniques in direct networks","volume":"2","author":"Ni","year":"1993","journal-title":"Computers"},{"key":"10.1016\/0166-218X(94)90180-5_BIB116","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/0218050","article-title":"An optimal synchronizer for the hypercube","volume":"18","author":"Peleg","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB117","series-title":"Tech. Rept. CMPT TR 93-10","article-title":"Bounded depth broadcasting","author":"Peters","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB118","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0190(92)90096-E","article-title":"Optimal total exchange for a 3-D torus","volume":"42","author":"Plateau","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB119","series-title":"Tech. Rept. CMPT TR 93-04","article-title":"Broadcasting in a torus network with wormhole routing","author":"Peters","year":"1993"},{"key":"10.1016\/0166-218X(94)90180-5_BIB120","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/358645.358660","article-title":"The cube connected cycles: a versatile network for parallel computation","volume":"24","author":"Preparata","year":"1981","journal-title":"Comm. ACM"},{"key":"10.1016\/0166-218X(94)90180-5_BIB121","doi-asserted-by":"crossref","unstructured":"P. Raghavan and E. Upfal, Efficient routing in all-optical networks, in: Proceedings of STOC '94, to appear.","DOI":"10.1145\/195058.195119"},{"key":"10.1016\/0166-218X(94)90180-5_BIB122","series-title":"Distributed Memory Computing","first-page":"1","article-title":"The new age of supercomputing","volume":"487","author":"Rattner","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB123","series-title":"Tech. Rept. RRR 21\u201386","article-title":"On the optimal strongly connected orientations of city street graphs III: three east-west avenues or north-south streets","author":"Roberts","year":"1986"},{"key":"10.1016\/0166-218X(94)90180-5_BIB124","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1137\/0401022","article-title":"On the optimal strongly connected orientations of city street graphs I: large grids","volume":"1","author":"Roberts","year":"1988","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0166-218X(94)90180-5_BIB125","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/net.3230190204","article-title":"On the optimal strongly connected orientations of city street graphs II: two east-west avenues or north-south streets","volume":"19","author":"Roberts","year":"1989","journal-title":"Networks"},{"key":"10.1016\/0166-218X(94)90180-5_BIB126","series-title":"Communication dans les R\u00e9seaux d'Interconnexion","author":"de Rumeur","year":"1994"},{"key":"10.1016\/0166-218X(94)90180-5_BIB127","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0743-7315(89)90045-2","article-title":"Data communication in hypercubes","volume":"6","author":"Saad","year":"1989","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB128","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0167-8191(89)90024-0","article-title":"Data communication in parallel architectures","volume":"11","author":"Saad","year":"1989","journal-title":"Parallel Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB129","article-title":"Broadcasting on linear arrays and meshes","author":"Seidel","year":"1993","journal-title":"Tech. Rept. ORNL\/TM-12356"},{"key":"10.1016\/0166-218X(94)90180-5_BIB130","article-title":"Circuit-switched vs. store and forward solutions to symmetric communication problems","author":"Seidel","year":"1989","journal-title":"Proceedings of the 4th Conference on Hypercube Concurrent Computers and Application"},{"key":"10.1016\/0166-218X(94)90180-5_BIB131","series-title":"CS-TR 90-06","article-title":"Concurrent bidirectional communication on the Intel iPSC860 and iPSC2","author":"Seidel","year":"1990"},{"key":"10.1016\/0166-218X(94)90180-5_BIB132","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(93)90086-O","article-title":"A broadcast algorithm in star graph interconnection networks","volume":"48","author":"Sheu","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB133","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0167-8191(05)80023-7","article-title":"Comments on broadcast algorithms for two-dimensional grids","volume":"17","author":"Simmen","year":"1991","journal-title":"Parallel Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB134","series-title":"Master thesis","article-title":"Circuit-switched structured communication on toroidal meshes","author":"Spencer","year":"1994"},{"key":"10.1016\/0166-218X(94)90180-5_BIB135","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(93)90099-U","article-title":"An efficient algorithm for multiple simultaneous broadcasts in the hypercube","volume":"46","author":"Stamoulis","year":"1993","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB136","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(91)90060-U","article-title":"Broadcasting in the butterfly network","volume":"39","author":"Stohr","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0166-218X(94)90180-5_BIB137","first-page":"226","article-title":"On the broadcast time of the butterfly network","author":"Stohr","year":"1991","journal-title":"WG 91: 17th International Workshop on Graphtheoretic Concepts in Computer Science"},{"key":"10.1016\/0166-218X(94)90180-5_BIB138","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0743-7315(90)90026-L","article-title":"Intensive hypercube communication, prearranged communication in link-bound machines","volume":"10","author":"Stout","year":"1990","journal-title":"J. Parallel Distributed Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB139","series-title":"Fast information sharing in a distributed system","author":"Sunderam","year":"1989"},{"key":"10.1016\/0166-218X(94)90180-5_BIB140","doi-asserted-by":"crossref","first-page":"1393","DOI":"10.1109\/12.247842","article-title":"Broadcasting on incomplete hypercubes","volume":"42","author":"Tien","year":"1993","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB141","series-title":"Distributed Memory Computing","first-page":"143","article-title":"Optimal multinode broadcast on a mesh connected graph with reduced bufferization","volume":"487","author":"Touzene","year":"1991"},{"key":"10.1016\/0166-218X(94)90180-5_BIB142","doi-asserted-by":"crossref","DOI":"10.1109\/71.207590","article-title":"Multinode broadcast in hypercubes and rings with randomly distributed length of packets","volume":"4","author":"Varvarigos","year":"1993","journal-title":"IEEE Trans. Parallel Distrib. Systems"},{"key":"10.1016\/0166-218X(94)90180-5_BIB143","doi-asserted-by":"crossref","first-page":"1233","DOI":"10.1016\/0167-8191(92)90068-I","article-title":"Communication algorithms for isotropic tasks in hypercube and wraparound meshes","volume":"18","author":"Varvarigos","year":"1992","journal-title":"Parallel Comput."},{"key":"10.1016\/0166-218X(94)90180-5_BIB144","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0220027","article-title":"The communication complexity of atomic commitment and of gossiping","volume":"20","author":"Wolfson","year":"1991","journal-title":"SIAM J. Comput."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X94901805?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0166218X94901805?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T02:28:30Z","timestamp":1555122510000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0166218X94901805"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":144,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["0166218X94901805"],"URL":"https:\/\/doi.org\/10.1016\/0166-218x(94)90180-5","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}