Binary linear programming models for robust broadcasting in communication networks
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 c -broadcasting, each node having the message completes up to c c transmissions to its neighbors over the communication lines in one time unit. In a k k -fault tolerant c c -broadcast network, the broadcasting process can be accomplished even if k k communication lines fail. This paper presents innovative binary linear programming formulations to construct c c -broadcast graphs, k k -fault-tolerant c c -broadcast graphs, and their time-relaxed versions. The proposed mathematical models are used to generate eight previously unknown minimum c c -broadcast graphs, new upper bounds for eleven other instances of the c c -broadcast problem, and over 30 minimum k k -fault-tolerant c c -broadcast graphs. The paper also provides a construction method to produce an upper bound for an infinite family of k k -fault-tolerant c c -broadcast graphs.
broadcasting communication networks integer programming fault-tolerant networks