References:

[1] R. Ahlswede, L. Gargano, H. S. Haroutunian, and L. H. Khachatrian. Faulttolerant
minimum broadcast networks. Networks, 27:293–307, 1996.
[2] R. Ahlswede, H. S. Haroutunian, and L. H. Khachatrian. Messy broadcasting
in networks. Kluwer International Series in Engineering and Computer Science,
pages 13–13, 1994.
[3] A. Bar-Noy, S. Guha, J. S. Naor, and B. Schieber. Multicasting in heterogeneous
networks. In Proceedings of the thirtieth annual ACM symposium on Theory of
computing, pages 448–453. ACM, 1998.
[4] B. Beauquier, S. Perennes, and O. Delmas. Tight bounds for broadcasting in the
linear cost model. Journal of Interconnection Networks, 2(02):175–188, 2001.
[5] R. Beier and J. F. Sibeyn. A powerful heuristic for telephone gossiping. Citeseer,
2000.
[6] J. C. Bermond, A. Ferreira, S. P´erennes, and J. G. Peters. Neighborhood broadcasting
in hypercubes. SIAM Journal on Discrete Mathematics, 21(4):823–843,
2007.
[7] J. C. Bermond, P. Fraigniaud, and J. G. Peters. Antepenultimate broadcasting.
Networks, 26(3):125–137, 1995.
[8] J. C. Bermond, H. A. Harutyunyan, A. L. Liestman, and S. Perennes. A note on
the dimentionality of modified Kn¨odel graphs. International Journal of Foundations
of Computer Science, 8:109–117, 1997.
68
[9] J. C. Bermond, P. Hell, A. L. Liestman, and J. G. Peters. Broadcasting in
bounded degree graphs. SIAM Journal on Discrete Mathematics, 5(1):10–24,
1992.
[10] J. C. Bermond, P. Hell, A. L. Liestman, and J. G. Peters. Sparse broadcast
graphs. Discrete applied mathematics, 36(2):97–130, 1992.
[11] S. C. Chau and A. L. Liestman. Constructing minimal broadcast networks.
Journal of Combinatorics, Information & System Science, 10:110–122, 1985.
[12] X. Chen. An upper bound for the broadcast function b (n). Chinese Journal of
Computers, 13:605–611, 1990.
[13] F. Comellas, H. A. Harutyunyan, and A. L. Liestman. Messy broadcasting in
mesh and torus networks. Journal of Interconnection Networks, pages 37–51,
2003.
[14] M. Cosnard and A. Ferreira. On the real power of loosely coupled parallel architectures.
Parallel Processing Letters, 1(02):103–111, 1991.
[15] R. Diestel. Graph theory, 2005.
[16] K. Diks and A. Pelc. Broadcasting with universal lists. In System Sciences, 1995.
Vol. II. Proceedings of the Twenty-Eighth Hawaii International Conference on,
volume 2, pages 564–573. IEEE, 1995.
[17] M. Dinneen, J. Ventura, M. Wilson, and G. Zakeri. Compound constructions of
minimal broadcast networks. Technical report, Department of Computer Science,
The University of Auckland, New Zealand, 1997.
[18] M. J. Dinneen, M. R. Fellows, and V. Faber. Algebraic constructions of efficient
broadcast networks. In Applied Algebra, Algebraic Algorithms and Error-
Correcting Codes, pages 152–158. Springer, 1991.
[19] M. Elkin and G. Kortsarz. Sublogarithmic approximation for telephone multicast:
path out of jungle (extended abstract). In SODA03: Proceedings of the
fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 76–85,
Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics.
69
[20] M. Elkin and G. Kortsarz. A combinatorial logarithmic approximation algorithm
for the directed telephone broadcast problem. SIAM Journal on Computing,
35(3):672–689, 2005.
[21] A. M. Farley. Minimal broadcast networks. Networks, 9(4):313–332, 1979.
[22] A. M. Farley, S. Hedetniemi, S. Mitchell, and A. Proskurowski. Minimum broadcast
graphs. Discrete Mathematics, 25(2):189–193, 1979.
[23] U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks.
Random Structures & Algorithms, 1(4):447–460, 1990.
[24] G. Fertin et al. A study of minimum gossip graphs. Discrete Mathematics,
215(1-3):33–58, 2000.
[25] G. Fertin, R. Labahn, et al. Compounding of gossip graphs. Networks, 36(2):126–
137, 2000.
[26] G. Fertin and A. Raspaud. Families of graphs having broadcasting and gossiping
properties. In Graph-Theoretic Concepts in Computer Science, pages 63–77.
Springer, 1998.
[27] G. Fertin and A. Raspaud. k-neighborhood broadcasting. In The Seventh International
Colloquium on Structural Information & Communication Complexity
(SIROCCO 2001), pages 133–146, 2001.
[28] G. Fertin and A. Raspaud. Neighborhood communications in networks. Electronic
Notes in Discrete Mathematics, 10:103–108, 2001.
[29] G. Fertin and A. Raspaud. A survey on Kn¨odel graphs. Discrete Applied Mathematics,
137:173–195, 2004.
[30] G. Fertin, A. Raspaud, H. Schr¨oder, O. S`ykora, and I. Vrt’o. Diameter of the
Kn¨odel graph. In Graph-Theoretic Concepts in Computer Science, pages 149–
160. Springer, 2000.
[31] P. Fraigniaud and E. Lazard. Methods and problems of communication in usual
networks. Discrete Applied Mathematics, 53(1):79–133, 1994.
70
[32] P. Fraigniaud and J. G. Peters. Minimum linear gossip graphs and maximal
linear (�, k)-gossip graphs. 1994.
[33] P. Fraigniaud and S. Vial. Approximation algorithms for broadcasting and gossiping.
Journal of Parallel and Distributed Computing, 43(1):47–55, 1997.
[34] P. Fraigniaud and S. Vial. Heuristic algorithms for personalized communication
problems in point-to-point networks. In 4th Colloquium on Structural Information
and Communication Complexity, pages 240–252, 1997.
[35] P. Fraigniaud and S. Vial. Comparison of heuristics for one-to-all and all-to-all
communications in partial meshes. Parallel Processing Letters, 9(01):9–20, 1999.
[36] S. Fujita, S. Perennes, and J. G. Peters. Neighbourhood gossiping in hypercubes.
Parallel Processing Letters, 8(02):189–195, 1998.
[37] L. Gargano and U. Vaccaro. On the construction of minimal broadcast networks.
Networks, 19(6):673–689, 1989.
[38] M. Grigni and D. Peleg. Tight bounds on mimimum broadcast networks. SIAM
Journal on Discrete Mathematics, 4(2):207–222, 1991.
[39] H. A. Haroutunian. New minimal broadcast networks. In Proceedings of 4th
International Colloquium on Coding Theory, pages 36–40, 1991.
[40] H. A. Harutyunyan. Minimum multiple message broadcast graphs. Networks,
47(4):218–224, 2006.
[41] H. A. Harutyunyan. An efficient vertex addition method for broadcast networks.
Internet Mathematics, 5(3):211–225, 2008.
[42] H. A. Harutyunyan, P. Hell, and A. L. Liestman. Messy broadcasting - decentralized
broadcast schemes with limited knowledge. Discrete Applied Mathematics,
159(5):322–327, 2011.
[43] H. A. Harutyunyan and A. L. Liestman. Messy broadcasting. Parallel Processing
Letters, 8(02):149–159, 1998.
[44] H. A. Harutyunyan and A. L. Liestman. More broadcast graphs. Discrete Applied
Mathematics, 98:81–102, 1999.
71
[45] H. A. Harutyunyan and A. L. Liestman. Improved upper and lower bounds for
k-broadcasting. Networks, 37(2):94–101, 2001.
[46] H. A. Harutyunyan and A. L. Liestman. k-broadcasting in trees. Networks,
38(3):163–168, 2001.
[47] H. A. Harutyunyan and A. L. Liestman. On the monotonicity of the broadcast
function. Discrete Mathematics, 262(1):149–157, 2003.
[48] H. A. Harutyunyan and A. L. Liestman. Upper bounds on the broadcast function
using minimum dominating sets. Discrete Mathematics, 312(20):2992–2996,
2012.
[49] H. A. Harutyunyan, A. L. Liestman, and B. Shao. A linear algorithm for finding
the k-broadcast center of a tree. Networks, 53(3):287–292, 2009.
[50] H. A. Harutyunyan and C. D. Morosan. An iterative algorithm for the minimum
broadcast time problem. In Proceedings of the 2nd IASTED International Conference
on Communication and Computer Networks, CCN04, Cambridge, MA,
USA, pages 447–452, 2004.
[51] H. A. Harutyunyan and C. D. Morosan. The spectra of Kn¨odel graphs. Informatica,
30:295–299, 2006.
[52] H. A. Harutyunyan and C. D. Morosan. On the minimum path problem in
Kn¨odel graphs. Networks, 50(1):86–91, 2007.
[53] H. A. Harutyunyan and B. Shao. A heuristic for k-broadcasting in arbitrary
networks. In Information Visualization, 2003. IV 2003. Proceedings. Seventh
International Conference on, pages 287–292. IEEE, 2003.
[54] H. A. Harutyunyan and B. Shao. Optimal k-broadcast in trees. Congressus
Numerantium, pages 117–128, 2003.
[55] H. A. Harutyunyan and B. Shao. An efficient heuristic for broadcasting in networks.
Journal of Parallel and Distributed Computing, 66(1):68–76, 2006.
[56] Hovhannes A Harutyunyan. Multiple message broadcasting in modified kn¨odel
graph. In The Seventh International Colloquium on Structural Information &
Communication Complexity (SIROCCO 2000), pages 157–165, 2000.
72
[57] S. M. Hedetniemi, S. T. Hedetniemi, and A. L. Liestman. A survey of gossiping
and broadcasting in communication networks. Networks, 18(4):319–349, 1988.
[58] M. C. Heydemann, N. Marlin, and S. P´erennes. Complete rotations in Cayley
graphs. European Journal of Combinatorics, 22(2):179–196, 2001.
[59] C. J. Hoelting, D. A. Schoenefeld, and R. L. Wainwright. A genetic algorithm
for the minimum broadcast time problem using a global precedence vector. In
Proceedings of the 1996 ACM symposium on Applied Computing, pages 258–262.
ACM, 1996.
[60] J. Hromkovic. Dissemination of information in communication networks: broadcasting,
gossiping, leader election, and fault-tolerance. Springer-Verlag, 2005.
[61] J. Hromkoviˇc, R. Klasing, B. Monien, and R. Peine. Dissemination of information
in interconnection networks (broadcasting & gossiping). In Combinatorial
network theory, pages 125–212. Springer, 1996.
[62] J. Hromkovic, R. Klasing, E. A. St¨ohr, E. A. St, et al. Dissemination of information
in vertex-disjoint paths mode, part 1: General bounds and gossiping in
hypercube-like networks. 1993.
[63] A. Jakoby, R. Reischuk, and C. Schindelhauer. The complexity of broadcasting in
planar and decomposable graphs. Discrete Applied Mathematics, 83(1):179–206,
1998.
[64] L. H. Khachatrian and H. S. Haroutunian. On optimal broadcast graphs. In
Proceedings of 4th International Colloquium on Coding Theory, Dilijan, pages
65–72, 1991.
[65] L. H. Khachatrian and O. S. Harutounian. Construction of new classes of minimal
broadcast networks. In Conference on Coding Theory, Armenia, 1990.
[66] W. Kn¨odel. New gossips and telephones. Discrete Mathematics, 13:95, 1975.
[67] J. C. K¨onig and E. Lazard. Minimum k-broadcast graphs. Discrete Applied
Mathematics, 53(1):199–209, 1994.
73
[68] G. Kortsarz and D. Peleg. Approximation algorithms for minimum-time broadcast.
SIAM Journal on Discrete Mathematics, 8(3):401–427, 1995.
[69] D. D. Kouvatsos and I. M. Mkwawa. Neighbourhood broadcasting schemes for
Cayley graphs with background traffic.
[70] D. D. Kouvatsos and I. M. Mkwawa. Broadcasting schemes for hypercubes with
background traffic. Journal of Systems and Software, 73(1):3–14, 2004.
[71] R. Labahn. A minimum broadcast graph on 63 vertices. Discrete Applied Mathematics,
53(1):247–250, 1994.
[72] C. Li, T. E. Hart, K. J. Henry, and I. A. Neufeld. Average-case messy broadcasting.
Journal of Interconnection Networks, 9(04):487–505, 2008.
[73] A. L. Liestman and J. G. Peters. Broadcast networks of bounded degree. SIAM
journal on Discrete Mathematics, 1(4):531–540, 1988.
[74] M. Maheo and J.-F. Sacl´e. Some minimum broadcast graphs. Discrete Applied
Mathematics, 53(1):275–285, 1994.
[75] E. Maraachlian. Optimal broadcasting in treelike graphs. PhD thesis, Concordia
University, 2010.
[76] S. Mitchell and S. Hedetniemi. A census of minimum broadcast graphs. Journal
of Combinatorics, Information and System Sciences, 5:141–151, 1980.
[77] I. M. Mkwawa and D. D. Kouvatsos. An optimal neighbourhood broadcasting
scheme for star interconnection networks. Journal of Interconnection Networks,
4(01):103–112, 2003.
[78] C. D. Morosan. Studies of interconnection networks with applications in broadcasting.
PhD thesis, Concordia University, 2007.
[79] J. H. Park and K. Y. Chwa. Recursive circulant: A new topology for multicomputer
networks. In Parallel Architectures, Algorithms and Networks, 1994.(ISPAN),
International Symposium on, pages 73–80. IEEE, 1994.
74
[80] K. Qiu and S. K. Das. A novel neighbourhood broadcasting algorithm on star
graphs. In Parallel and Distributed Systems, 2002. Proceedings. Ninth International
Conference on, pages 37–41. IEEE, 2002.
[81] R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast
time. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium
on, pages 202–213. IEEE, 1994.
[82] J. F. Sacl´e. Lower bounds for the size in four families of minimum broadcast
graphs. Discrete Mathematics, 150(1):359–369, 1996.
[83] P. Scheuermann and G. Wu. Heuristic algorithms for broadcasting in point-topoint
computer networks. Computers, IEEE Transactions on, 100(9):804–811,
1984.
[84] C. Schindelhauer. On the inapproximability of broadcasting time. In Approximation
Algorithms for Combinatorial Optimization, pages 226–237. Springer,
2000.
[85] B. Shao. A heuristic for broadcasting in arbitrary networks. Master’s thesis,
Concordia University, 2003.
[86] B. Shao. On k-broadcasting in graphs. PhD thesis, Concordia University, 2006.
[87] Peter J. Slater, Ernest J. Cockayne, and S. T. Hedetniemi. Information dissemination
in trees. SIAM Journal on Computing, 10(4):692–701, 1981.
[88] J. A. Ventura and X. Weng. A new method for constructing minimal broadcast
networks. Networks, 23(5):481–497, 1993.
[89] M. X. Weng and J. A. Ventura. A doubling procedure for constructing minimal
broadcast networks. Telecommunication Systems, 3(3):259–293, 1994.
[90] J. Xiao and X.Wang. A research on minimum broadcast graphs. Chinese Journal
of Computers, 11:99–105, 1988.
[91] X. Xu. Broadcast networks on 2p − 1 nodes and minimum broadcast network on
127 nodes. Master’s thesis, Concordia University, 2004.
75
[92] J. G. Zhou and K. M. Zhang. A minimum broadcast graph on 26 vertices. Applied
mathematics letters, 14(8):1023–1026, 2001.