Improved Approximation for Broadcasting in k-Path Graphs

Broadcasting is an information dissemination primitive where a message is passed from one node (called originator) to all other nodes in the network. With the increasing interest in interconnection networks, an extensive amount of research was dedicated to broadcasting. Two main research goals of this area are finding inexpensive network structures that maintain efficient broadcasting and finding the broadcast time for well-known and widely used network topologies. In the scope of this paper, we will mainly focus on determining the broadcast time and the optimal broadcasting scheme for graphs. Determination of the broadcast time of a node x in an arbitrary network G is known to be NP-hard. Polynomial time solutions are known only for a few classes of networks. There also exist various heuristic and approximation algorithms for different network topologies. In this paper, we will consider networks that can be represented as k-path graphs. We will present a polynomial time 2-approximation algorithm for the broadcast time problem in k-path graphs.