An algorithm for constructing minimal c-broadcast networks

Shiwoo Lee, José A. Ventura

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

c-Broadcasting is a special process to disseminate a single message, originated at any node in a network, to all other nodes of the network by letting each informed node transmit the message to at most c neighbors simultaneously. A minimal c-broadcast network (c-mbn) is a communication network in which c-broadcasting can be completed in minimum time from any node. An optimal c-broadcast network (c-obn) is a c-mbn with the smallest number of edges. Previous studies showed that c-obn's are extremely difficult to find. A network compounding algorithm is proposed to construct sparse c-mbn's with n1n2 - i nodes by connecting a subset of nodes from several copies of a c-mbn with n1 nodes using the structure of another c-mbn with n2 nodes, such that n1 ≥ 1 and 0 ≤ i < n2, satisfying [logc+1(n1n2 - i)] = [logc+1 n1] + [logc+1n2]. Computational results are also provided.

Original languageEnglish (US)
Pages (from-to)6-21
Number of pages16
JournalNetworks
Volume38
Issue number1
DOIs
StatePublished - Aug 2001

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'An algorithm for constructing minimal c-broadcast networks'. Together they form a unique fingerprint.

Cite this