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

Preview |
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. 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.

Repository Staff Only: item control page