Sparse hypercube – a minimal \(k\)-line broadcast graph. (English) Zbl 1057.68078
Summary: This paper proposes methods for reducing the maximum degree of vertices in graphs that maintain optimal broadcast time when a vertex can call a vertex at distance at most \(k\) during any time unit. The basic idea behind the proposed construction method is to eliminate edges from binary \(n\)-cubes. We show that, by this approach, the maximum degree of a vertex can be reduced to at most \((2k-1)\lceil\sqrt{\log_2|V|-k}\rceil\), where \(2\leq k<\log_2|V|\), which asymptotically achieves the lower bound provided \(|V|=2^n\) and a constant \(k\).
References:
| [1] | Abraham, S.; Padmanabhan, K., Twisted cubes: a study in asymmetry, IEEE Trans. Parallel Distributed Systems, 13, 104-110 (1991) |
| [2] | B. Aiello, T. Leighton, Coding theory, hypercube embeddings, and fault tolerance, in: Proceedings of the Third SPAA, ACM, 1991, pp. 125-136.; B. Aiello, T. Leighton, Coding theory, hypercube embeddings, and fault tolerance, in: Proceedings of the Third SPAA, ACM, 1991, pp. 125-136. |
| [3] | Banerjee, P., The cubical ring connected cycles: a fault-tolerant parallel computation network, IEEE Trans. Comput., 37, 5, 632-636 (1988) |
| [4] | Bermond, J.-C.; Fraigniaud, P.; Peters, J. P., Antepenultimate broadcasting, Networks, 26, 125-137 (1995) · Zbl 0856.90046 |
| [5] | Bermond, J.-C.; Hell, P.; Liestman, A. L.; Peters, J. P., Sparse broadcast graphs, Discrete Appl. Math., 36, 97-130 (1992) · Zbl 0764.05042 |
| [6] | Chau, S. C.; Liestman, A. L., Constructing minimal broadcast networks, J. Combin. Inform. System Sci., 10, 110-122 (1985) · Zbl 0696.90077 |
| [7] | Dally, W. J.; Seitz, C. L., Deadlock-free message routing in multiprocessor interconnection network, IEEE Trans. Comput., 36, 5, 547-553 (1987) · Zbl 0617.68037 |
| [8] | M.J. Dinneen, M.R. Fellows, V. Faber, Algebraic constructions of efficient broadcast networks, in: Proceedings of Ninth AAECC Meeting, Lecture Notes in Computer Science, Vol. 539, 1991, pp. 152-158.; M.J. Dinneen, M.R. Fellows, V. Faber, Algebraic constructions of efficient broadcast networks, in: Proceedings of Ninth AAECC Meeting, Lecture Notes in Computer Science, Vol. 539, 1991, pp. 152-158. · Zbl 0767.94028 |
| [9] | Dinneen, M. J.; Ventura, J. A.; Wilson, M. C.; Zakeri, G., Compound constructions of minimal broadcast networks, Discrete Appl. Math., 93, 205-232 (1999) · Zbl 0941.90009 |
| [10] | Efe, K., A variation on the hypercube with lower diameter, IEEE Trans. Comput., 40, 11, 1312-1316 (1991) |
| [11] | El-Amawy, A.; Latifi, S., Properties and performance of folded hypercubes, IEEE Trans. Parallel Distributed Systems, 2, 1, 31-42 (1991) |
| [12] | Esfahanian, A. H.; Ni, L. M.; Sagan, B. E., The twisted \(N\)-cube with application to multiprocessing, IEEE Trans. Comput., 40, 1, 88-93 (1991) · Zbl 1395.05139 |
| [13] | Farley, A. M., Minimal broadcast networks, Networks, 9, 313-332 (1979) · Zbl 0425.94025 |
| [14] | Farley, A. M., Minimum-time line broadcast networks, Networks, 10, 59-70 (1980) · Zbl 0432.90030 |
| [15] | Farley, A. M.; Hedetniemi, S. T.; Mitchell, S. L.; Proskurowski, A., Minimum broadcast graphs, Discrete Math., 25, 189-193 (1979) · Zbl 0404.05038 |
| [16] | Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discrete Appl. Math., 53, 79-133 (1994) · Zbl 0818.94029 |
| [17] | P. Fraigniaud, J.G. Peters, Minimum linear gossip graphs and maximal linear \((Δk\); P. Fraigniaud, J.G. Peters, Minimum linear gossip graphs and maximal linear \((Δk\) · Zbl 0993.94026 |
| [18] | Gargano, L.; Vaccaro, U., On the construction of minimal broadcast networks, Networks, 19, 673-689 (1989) · Zbl 0676.90021 |
| [19] | Harutyunyan, H. A.; Liestman, A. L., More broadcast graphs, Discrete Appl. Math., 98, 81-102 (1999) · Zbl 0936.05059 |
| [20] | Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047 |
| [21] | P.A.J. Hilbers, M.R.J. Koopman, J.L.A. Snepscheut, The twisted cube, in: Proceedings of PARLE’91: Parallel Architectures and Languages Europe, Lecture Notes in Computer Science, Vol. 506, Springer, Berlin, 1987, pp. 152-159.; P.A.J. Hilbers, M.R.J. Koopman, J.L.A. Snepscheut, The twisted cube, in: Proceedings of PARLE’91: Parallel Architectures and Languages Europe, Lecture Notes in Computer Science, Vol. 506, Springer, Berlin, 1987, pp. 152-159. |
| [22] | J. Hromkovič, R. Klasing, B. Monien, R. Peine, Dissemination of information in interconnection networks (Broadcasting and Gossiping); in: F. Hsu, D.-Z. Du (Eds.), Combinatorial Network Theory, Science Press & AMS, to appear.; J. Hromkovič, R. Klasing, B. Monien, R. Peine, Dissemination of information in interconnection networks (Broadcasting and Gossiping); in: F. Hsu, D.-Z. Du (Eds.), Combinatorial Network Theory, Science Press & AMS, to appear. · Zbl 0840.68088 |
| [23] | L.H. Khachatrian, H.S. Haroutunian, Construction of new classes of minimal broadcast networks, in: Proceedings of Third International Colloquium on Coding Theory, 1990, pp. 69-77.; L.H. Khachatrian, H.S. Haroutunian, Construction of new classes of minimal broadcast networks, in: Proceedings of Third International Colloquium on Coding Theory, 1990, pp. 69-77. |
| [24] | Kwon, O.-H.; Chwa, K.-Y., Multiple messages broadcasting in communication networks, Networks, 26, 253-261 (1995) · Zbl 0856.90048 |
| [25] | Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan Kaufmann Publishers, Inc: Morgan Kaufmann Publishers, Inc Los Altos, CA · Zbl 0743.68007 |
| [26] | Leiserson, C. E., Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Trans. Comput., C-34, 10, 892-901 (1985) |
| [27] | Preparata, F. P.; Vuillemin, J., The cube-connected cyclesa versatile network for parallel computation, Comm. ACM, 24, 5, 300-309 (1981) |
| [28] | Roman, S., Coding and Information Theory (1992), Springer: Springer Berlin · Zbl 0752.94001 |
| [29] | Sibai, F. N.; Abonamah, A. A., The full-cube topology: properties and routing, Inform. Sci., 76, 1-2, 111-129 (1994) |
| [30] | Varman, P. J.; Doshi, K., Sorting with linear speedup on a pipelined hypercube, IEEE Trans. Comput., 41, 1, 97-103 (1992) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
