Minimum-cost line broadcast in paths

AbstractUnder the line communication protocol, calls can be placed between pairs of non-adjacent sites over a path of lines connecting them; only one call can utilize a line at any time. This paper addresses questions regarding the cumulative cost, i.e., sum of lengths of calls, of broadcasting under the line protocol in path networks. Let Pn be the path with n vertices, and Cn be the cost of an optimal, line broadcast scheme from a terminal vertex in path Pn. We show that a minimum-cost line broadcast scheme from any source vertex in Pn has cost no more than Cn and no less than Cn − n + 2 for any n ⩾ 2 and any time t > [log2n]. We derive a closed-form expression for the minimum cost of a minimum-time line broadcast from a terminal vertex in certain paths and relate this to costs from nearby sources