$k$-Port Line Broadcasting in Trees

Abstract

Broadcasting is the process of message transmission in a communication network. The communication network is modeled by a graph $G=(V,E)$, where the set of vertices $V$ represents the network members and the set of edges $E$ represents the communication links between two given vertices. We assume that $G$ is connected and undirected. One vertex, called the \emph{originator} of the graph, holds a message that has to be transmitted to all vertices of the network by placing a series of calls over the network.

A \textbf{k-port} line broadcasting in $G$ is a model in which an informed vertex can call, at each time unit, at most $k$ vertices and transmit a message through a path, as long as two transmissions do not use the same edge at the same time. In case $k$ is not bounded, the model is called the all-port line model.

In this paper, we extend Cohen’s work $[6]$, which handles the all-port line model.