TY - JOUR
T1 - Binary linear programming models for robust broadcasting in communication networks
AU - McGarvey, Ronald G.
AU - Rieksts, Brian Q.
AU - Ventura, José A.
AU - Ahn, Namsu
N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2016/5/11
Y1 - 2016/5/11
N2 - Broadcasting is an information dissemination process in communication networks whereby a message, originated at any node of a network, is transmitted to all other nodes of the network. In c-broadcasting, each node having the message completes up to c transmissions to its neighbors over the communication lines in one time unit. In a k-fault tolerant c-broadcast network, the broadcasting process can be accomplished even if k communication lines fail. This paper presents innovative binary linear programming formulations to construct c-broadcast graphs, k-fault-tolerant c-broadcast graphs, and their time-relaxed versions. The proposed mathematical models are used to generate eight previously unknown minimum c-broadcast graphs, new upper bounds for eleven other instances of the c-broadcast problem, and over 30 minimum k-fault-tolerant c-broadcast graphs. The paper also provides a construction method to produce an upper bound for an infinite family of k-fault-tolerant c-broadcast graphs.
AB - Broadcasting is an information dissemination process in communication networks whereby a message, originated at any node of a network, is transmitted to all other nodes of the network. In c-broadcasting, each node having the message completes up to c transmissions to its neighbors over the communication lines in one time unit. In a k-fault tolerant c-broadcast network, the broadcasting process can be accomplished even if k communication lines fail. This paper presents innovative binary linear programming formulations to construct c-broadcast graphs, k-fault-tolerant c-broadcast graphs, and their time-relaxed versions. The proposed mathematical models are used to generate eight previously unknown minimum c-broadcast graphs, new upper bounds for eleven other instances of the c-broadcast problem, and over 30 minimum k-fault-tolerant c-broadcast graphs. The paper also provides a construction method to produce an upper bound for an infinite family of k-fault-tolerant c-broadcast graphs.
UR - http://www.scopus.com/inward/record.url?scp=84949640401&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84949640401&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2015.11.008
DO - 10.1016/j.dam.2015.11.008
M3 - Article
AN - SCOPUS:84949640401
SN - 0166-218X
VL - 204
SP - 173
EP - 184
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -