The complexity of systolic dissemination of information in interconnection networks
Hromkovič, J. ; Klasing, R. ; Unger, W. ; Wagener, H. ; Pardubská, D.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 303-342 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@article{ITA_1994__28_3-4_303_0,
     author = {Hromkovi\v c, J. and Klasing, R. and Unger, W. and Wagener, H. and Pardubsk\'a, D.},
     title = {The complexity of systolic dissemination of information in interconnection networks},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {303-342},
     mrnumber = {1282451},
     zbl = {0888.68014},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_3-4_303_0}
}

Hromkovič, J.; Klasing, R.; Unger, W.; Wagener, H.; Pardubská, D. The complexity of systolic dissemination of information in interconnection networks. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 303-342. http://gdmltest.u-ga.fr/item/ITA_1994__28_3-4_303_0/

[BHMS90] A. Bagchi, S. L. Hakimi, J. Mitchem and E. Schmeichel, Parallel algorithms for gossiping by mail, Information, Process. Letters, 1990, 34, pp. 197-202. | MR 1060435 | Zbl 0696.68048

[CC84] C. Choffrut and K. Culik Ii, On real-time cellular automata and trellis automata, Acta Informatica, 1984, 21, pp. 393-407. | MR 767316 | Zbl 0534.68039

[CGS83] K. Culik Ii, J. Gruska and A. Salomaa, Systolic automata for VLSI on balanced trees, Acta Informatica, 1983, 18, pp. 335-344. | MR 691733 | Zbl 0493.68054

[CGS84] K. Culik Ii, J. Gruska and A. Salomaa, Systolic trellis automata. Part I, Intern. J. Comput. Math., 1984, 15, pp. 195-212. | MR 754266 | Zbl 0571.68041

[CSW84] K. Culik Ii, A. Salomaa and D. Wood, Systolic tree acceptors, R.A.I.R.O. Theoretical Informatics, 1984, 18, pp. 53-69. | Numdam | MR 750451 | Zbl 0571.68043

[FHMMM92] R. Feldmann, J. Hromkovič, S. Madhavapeddy, B. Monien and P. Mysliwietz, Optimal algorithms for dissemination of information in generalized communication modes, Proc. PARLE'92, Springer-Verlag, Lecture Notes in Computer Science, 1992, 605, pp. 115-130. | MR 1230238

[HHL88] S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestmann, A survey of gossiping and broadcasting in communication networks, Networks, 1988, 18, pp. 319-349. | MR 964236 | Zbl 0649.90047

[HJM93] J. Hromkovič, C.-D. Jeschke and B. Monien, Note an optimal gossiping in some weak-connected graphs, Theoretical Computer Science (to appear). | MR 1275825 | Zbl 0824.68010

[HKMP93] J. Hromkovič, R. Klasing, B. Monien and R. Peine, Dissemination of information in interconnection networks (broadcasting & gossiping), In Combinatorial Network Theory (Frank Hsu, Ding-Zhu Du, Eds), Science Press, AMS 1993 (to appear). | MR 1382871 | Zbl 0840.68088

[IK84] O. H. Ibarra and S. M. Kim, Characterizations and computational complexity of systolic trellis automata, Theoretical Computer Science, 1984, 29, pp. 123-153. | MR 742405 | Zbl 0536.68048

[IKM85] O. H. Ibarra, S. M. Kim and S. Moran, Sequential machine characterizations of trellis and cellular automata and applications, SIAM J. Comput., 1985, 14, pp. 426-447. | MR 784748 | Zbl 0574.68044

[IPK85] O. H. Ibarra, M. A. Palis and S. M. Kim, Fast parallel language recognition by cellular automata, Theoretical Computer Science, 1985, 41, pp. 231-246. | MR 847679 | Zbl 0591.68054

[Ku79] H. T. Kung, Let's design algorithms for VLSI systems, In Proc. of the Caltech Conference of VLSI (CL. L. Seifz Ed.), Pasadena, California, 1979, pp. 65-90.

[LHL93] R. Labahn, S. T. Hedetniemi and R. Laskar, Periodic gossiping on trees, in Discrete Applied Mathematics (to appear). | MR 1291010 | Zbl 0836.68085

[LR93a] A. L. Liestman and D. Richards, Perpetual gossiping, Technical Report, Simon Fraser University, Vancouver, Canada, 1993. | MR 1279556

[LR93b] A. L. Liestman and D. Richards, Network communication in edge-colored graphs: Gossiping, IEEE Trans. Par. Distr. Syst., 1993, 4, pp. 438-445.

[MS90] B. Monien and I. H. Sudborough, Embedding one interconnection network in another, Computing Suppl., 1990, 7, pp. 257-282. | MR 1059934 | Zbl 0699.68017