Altay, Sirma Cagil (2013) A general upper bound on broadcast function B(n) using Knodel graph. Masters thesis, Concordia University.

Text (application/pdf)
459kBAltay_MSc_F2013.pdf  Accepted Version Available under License Spectrum Terms of Access. 
Abstract
Broadcasting in a graph is the process of transmitting a message from one vertex, the originator, to all other vertices of the graph. We will consider the classical model in which an informed vertex can only inform one of its uninformed neighbours during each time unit. A broadcast graph on n vertices is a graph in which broadcasting can be completed in ceiling of log n to the base 2 time units from any originator. A minimum broadcast graph on n vertices is a broadcast graph that has the least possible number of edges, B(n), over all broadcast graphs on n vertices. This thesis enhances studies about broadcasting by applying a vertex deletion method to a specific graph topology, namely Knodel graph, in order to construct broadcast graphs on odd number of vertices. This construction provides an improved general upper bound on B(n) for all odd n except when n=2^k−1.
Divisions:  Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering 

Item Type:  Thesis (Masters) 
Authors:  Altay, Sirma Cagil 
Institution:  Concordia University 
Degree Name:  M. Comp. Sc. 
Program:  Computer Science 
Date:  15 September 2013 
Thesis Supervisor(s):  Harutyunyan, Hovhannes 
Keywords:  Broadcasting, Broadcast graph, Minimum broadcast graph, Knodel graph, Broadcast function B(n) 
ID Code:  977799 
Deposited By:  SIRMA CAGIL ALTAY 
Deposited On:  26 Nov 2013 15:36 
Last Modified:  18 Jan 2018 17:45 
References:
[1] R. Ahlswede, L. Gargano, H. S. Haroutunian, and L. H. Khachatrian. Faulttolerantminimum 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. BarNoy, 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 TwentyEighth 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 ACMSIAM 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(13):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 GraphTheoretic Concepts in Computer Science, pages 63–77.
Springer, 1998.
[27] G. Fertin and A. Raspaud. kneighborhood 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 GraphTheoretic 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 pointtopoint networks. In 4th Colloquium on Structural Information
and Communication Complexity, pages 240–252, 1997.
[35] P. Fraigniaud and S. Vial. Comparison of heuristics for onetoall and alltoall
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
kbroadcasting. Networks, 37(2):94–101, 2001.
[46] H. A. Harutyunyan and A. L. Liestman. kbroadcasting 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 kbroadcast 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 kbroadcasting 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 kbroadcast 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 faulttolerance. SpringerVerlag, 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 vertexdisjoint paths mode, part 1: General bounds and gossiping in
hypercubelike 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 kbroadcast graphs. Discrete Applied
Mathematics, 53(1):199–209, 1994.
73
[68] G. Kortsarz and D. Peleg. Approximation algorithms for minimumtime 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. Averagecase 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 pointtopoint
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 kbroadcasting 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.
Repository Staff Only: item control page