Top

Published in:

2017 | OriginalPaper | Chapter

Broadcast Graphs Using New Dimensional Broadcast Schemes for Knödel Graphs

Authors : Hovhannes A. Harutyunyan, Zhiyuan Li

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Broadcasting is an information disseminating process of distributing a message from an originator vertex v of graph \(G=(V,E)\) to all of its vertices. The broadcast time of vertex v is the minimum possible time required to broadcast from v in graph G. A graph G on n vertices is called broadcast graph if broadcasting from any originator in G can be accomplished in \(\lceil \log n\rceil \) time. A broadcast graph with the minimum number of edges is called minimum broadcast graph. The number of edges in a minimum broadcast graph on n vertices is denoted by B(n). Finding the values of B(n) is very difficult. A large number of papers present techniques to construct broadcast graphs and to obtain upper bounds on B(n). In this paper, we first find new dimensional broadcast schemes for Knödel graphs, and then use them to give a general upper bound on B(n) for almost all odd n.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Group Distance Magic Labeling of

next chapter Incremental Algorithms to Update Visibility Polygons

Averbuch, A., Shabtai, R.H., Roditty, Y.: Efficient construction of broadcast graphs. Discret. Appl. Math. 171, 9–14 (2014)MathSciNetCrossRefMATH

Barsky, G., Grigoryan, H., Harutyunyan, H.A.: Tight lower bounds on broadcast function for n = 24 and 25. Discret. Appl. Math. 175, 109–114 (2014)MathSciNetCrossRefMATH

Bermond, J.-C., Fraigniaud, P., Peters, J.G.: Antepenultimate broadcasting. Networks 26, 125–137 (1995)MathSciNetCrossRefMATH

Bermond, J.-C., Harutyunyan, H.A., Liestman, A.L., Perennes, S.: A note on the dimensionality of modified Knödel graphs. Int. J. Found. Comput. Sci. 8(02), 109–116 (1997)CrossRefMATH

Bermond, J.-C., Hell, P., Liestman, A.L., Peters, J.G.: Sparse broadcast graphs. Discret. Appl. Math. 36, 97–130 (1992)MathSciNetCrossRefMATH

Chau, S.C., Liestman, A.L.: Constructing minimal broadcast networks. J. Comb. Inf. Syst. Sci. 10, 110–122 (1985)MathSciNetMATH

Dinneen, M.J., Fellows, M.R., Faber, V.: Algebraic constructions of efficient broadcast networks. In: Mattson, H.F., Mora, T., Rao, T.R.N. (eds.) AAECC 1991. LNCS, vol. 539, pp. 152–158. Springer, Heidelberg (1991). doi:10.1007/3-540-54522-0_104 CrossRef

Dinneen, M.J., Ventura, J.A., Wilson, M.C., Zakeri, G.: Compound constructions of broadcast networks. Discret. Appl. Math. 93, 205–232 (1999)MathSciNetCrossRefMATH

Farley, A.M.: Minimal broadcast networks. Networks 9, 313–332 (1979)MathSciNetCrossRefMATH

10.

Farley, A.M., Hedetniemi, S., Mitchell, S., Proskurowski, A.: Minimum broadcast graphs. Discret. Math. 25, 189–193 (1979)MathSciNetCrossRefMATH

11.

Fertin, G., Raspaud, A.: A survey on Knödel graphs. Discret. Appl. Math. 137, 173–195 (2004)CrossRefMATH

12.

Gargano, L., Vaccaro, U.: On the construction of minimal broadcast networks. Networks 19, 673–689 (1989)MathSciNetCrossRefMATH

13.

Grigni, M., Peleg, D.: Tight bounds on mimimum broadcast networks. SIAM J. Discret. Math. 4, 207–222 (1991)CrossRefMATH

14.

Grigoryan, H., Harutyunyan, H.A.: New lower bounds on broadcast function. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 174–184. Springer, Heidelberg (2014). doi:10.1007/978-3-319-07956-1_16

15.

Harutyunyan, H.A.: An efficient vertex addition method for broadcast networks. Internet Math. 5(3), 197–211 (2009)MathSciNet

16.

Harutyunyan, H.A., Li, Z.: A new construction of broadcast graphs. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, vol. 9602, pp. 201–211. Springer, Heidelberg (2016). doi:10.1007/978-3-319-29221-2_17 CrossRef

17.

Harutyunyan, H.A., Liestman, A.L.: More broadcast graphs. Discret. Appl. Math. 98, 81–102 (1999)MathSciNetCrossRefMATH

18.

Harutyunyan, H.A., Liestman, A.L.: Improved upper and lower bounds for k-broadcasting. Networks 37, 94–101 (2001)MathSciNetCrossRefMATH

19.

Harutyunyan, H.A., Liestman, A.L.: Upper bounds on the broadcast function using minimum dominating sets. Discret. Math. 312, 2992–2996 (2012)MathSciNetCrossRefMATH

20.

Harutyunyan, H.A., Liestman, A.L., Peters, J.G., Richards, D.: Broadcasting and gossiping. In: Handbook of Graph Theorey, pp. 1477–1494. Chapman and Hall (2013)

21.

Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks 18, 319–349 (1988)MathSciNetCrossRefMATH

22.

Khachatrian, L.H., Harutounian, H.S.: Construction of new classes of minimal broadcast networks. In: Conference on Coding Theory, Dilijan, Armenia, pp. 69–77 (1990)

23.

Knödel, W.: New gossips and telephones. Discret. Math. 13, 95 (1975)MathSciNetCrossRefMATH

24.

Labahn, R.: A minimum broadcast graph on 63 vertices. Discret. Appl. Math. 53, 247–250 (1994)MathSciNetCrossRefMATH

25.

Maheo, M., Saclé, J.-F.: Some minimum broadcast graphs. Discret. Appl. Math. 53, 275–285 (1994)MathSciNetCrossRefMATH

26.

Mitchell, S., Hedetniemi, S.: A census of minimum broadcast graphs. J. Comb. Inf. Syst. Sci. 5, 141–151 (1980)MathSciNetMATH

27.

Park, J.-H., Chwa, K.-Y.: Recursive circulant: a new topology for multicomputer networks. In: International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), pp. 73–80. IEEE (1994)

28.

Saclé, J.-F.: Lower bounds for the size in four families of minimum broadcast graphs. Discret. Math. 150, 359–369 (1996)MathSciNetCrossRefMATH

29.

Shao, B.: On K-broadcasting in graphs. Ph.D. thesis, Concordia University (2006)

30.

Ventura, J.A., Weng, X.: A new method for constructing minimal broadcast networks. Networks 23, 481–497 (1993)MathSciNetCrossRefMATH

31.

Weng, M.X., Ventura, J.A.: A doubling procedure for constructing minimal broadcast networks. Telecommun. Syst. 3, 259–293 (1994)CrossRef

32.

Xiao, J., Wang, X.: A research on minimum broadcast graphs. Chin. J. Comput. 11, 99–105 (1988)

33.

Zhou, J., Zhang, K.: A minimum broadcast graph on 26 vertices. Appl. Math. Lett. 14, 1023–1026 (2001)MathSciNetCrossRefMATH

Title: Broadcast Graphs Using New Dimensional Broadcast Schemes for Knödel Graphs
Authors: Hovhannes A. Harutyunyan
Zhiyuan Li
Publisher: Springer International Publishing
Book: Algorithms and Discrete Applied Mathematics
Print ISBN: 978-3-319-53006-2

Electronic ISBN: 978-3-319-53007-9

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-53007-9_18

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner