A doubling procedure for constructing minimal broadcast networks

Michael X. Weng; Jose Antonio Ventura

doi:10.1007/BF02110308

A doubling procedure for constructing minimal broadcast networks

Michael X. Weng, Jose Antonio Ventura

Marcus Department of Industrial and Manufacturing Engineering

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

Broadcast is the task of disseminating a message from any node to all the other nodes in a network. A minimal broadcast network (mbn) with n nodes is a communication network in which a message originated at any node can be broadcasted in [log₂n] time units. An optimal broadcast network (obn) is an mbn with minimum number of edges. No method is known for constructing an obn with an arbitrary number of nodes. In this paper, a new method called the doubling procedure is presented to construct mbn's with 2 n and 2 n-1 nodes when an obn or a good mbn with n nodes is known. The new construction method is based on the concepts of center node and center node set of an mbn. An algorithm is proposed to find a center node set of a given mbn. It is shown that an obn with 2 n nodes can be constructed based on a known obn with n nodes for all n ≤ 9, n=15, 31 and 63, n=2^m-1 and n=2^m, mεZ⁺, by applying the doubling procedure. This method also generates the best mbn's for some values of [n≤64.

Original language	English (US)
Pages (from-to)	259-293
Number of pages	35
Journal	Telecommunication Systems
Volume	3
Issue number	3
DOIs	https://doi.org/10.1007/BF02110308
State	Published - Oct 1 1994

All Science Journal Classification (ASJC) codes

Electrical and Electronic Engineering

Access to Document

10.1007/BF02110308

Cite this

@article{5c596b56b5034a33a9acd3c48391d6b5,

title = "A doubling procedure for constructing minimal broadcast networks",

abstract = "Broadcast is the task of disseminating a message from any node to all the other nodes in a network. A minimal broadcast network (mbn) with n nodes is a communication network in which a message originated at any node can be broadcasted in [log2n] time units. An optimal broadcast network (obn) is an mbn with minimum number of edges. No method is known for constructing an obn with an arbitrary number of nodes. In this paper, a new method called the doubling procedure is presented to construct mbn's with 2 n and 2 n-1 nodes when an obn or a good mbn with n nodes is known. The new construction method is based on the concepts of center node and center node set of an mbn. An algorithm is proposed to find a center node set of a given mbn. It is shown that an obn with 2 n nodes can be constructed based on a known obn with n nodes for all n ≤ 9, n=15, 31 and 63, n=2m-1 and n=2m, mεZ+, by applying the doubling procedure. This method also generates the best mbn's for some values of [n≤64.",

author = "Weng, {Michael X.} and Ventura, {Jose Antonio}",

year = "1994",

month = oct,

day = "1",

doi = "10.1007/BF02110308",

language = "English (US)",

volume = "3",

pages = "259--293",

journal = "Telecommunication Systems",

issn = "1018-4864",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - A doubling procedure for constructing minimal broadcast networks

AU - Weng, Michael X.

AU - Ventura, Jose Antonio

PY - 1994/10/1

Y1 - 1994/10/1

N2 - Broadcast is the task of disseminating a message from any node to all the other nodes in a network. A minimal broadcast network (mbn) with n nodes is a communication network in which a message originated at any node can be broadcasted in [log2n] time units. An optimal broadcast network (obn) is an mbn with minimum number of edges. No method is known for constructing an obn with an arbitrary number of nodes. In this paper, a new method called the doubling procedure is presented to construct mbn's with 2 n and 2 n-1 nodes when an obn or a good mbn with n nodes is known. The new construction method is based on the concepts of center node and center node set of an mbn. An algorithm is proposed to find a center node set of a given mbn. It is shown that an obn with 2 n nodes can be constructed based on a known obn with n nodes for all n ≤ 9, n=15, 31 and 63, n=2m-1 and n=2m, mεZ+, by applying the doubling procedure. This method also generates the best mbn's for some values of [n≤64.

AB - Broadcast is the task of disseminating a message from any node to all the other nodes in a network. A minimal broadcast network (mbn) with n nodes is a communication network in which a message originated at any node can be broadcasted in [log2n] time units. An optimal broadcast network (obn) is an mbn with minimum number of edges. No method is known for constructing an obn with an arbitrary number of nodes. In this paper, a new method called the doubling procedure is presented to construct mbn's with 2 n and 2 n-1 nodes when an obn or a good mbn with n nodes is known. The new construction method is based on the concepts of center node and center node set of an mbn. An algorithm is proposed to find a center node set of a given mbn. It is shown that an obn with 2 n nodes can be constructed based on a known obn with n nodes for all n ≤ 9, n=15, 31 and 63, n=2m-1 and n=2m, mεZ+, by applying the doubling procedure. This method also generates the best mbn's for some values of [n≤64.

UR - http://www.scopus.com/inward/record.url?scp=0001212295&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001212295&partnerID=8YFLogxK

U2 - 10.1007/BF02110308

DO - 10.1007/BF02110308

M3 - Article

AN - SCOPUS:0001212295

SN - 1018-4864

VL - 3

SP - 259

EP - 293

JO - Telecommunication Systems

JF - Telecommunication Systems

IS - 3

ER -

A doubling procedure for constructing minimal broadcast networks

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this