Minimum-cost line broadcast in paths

✍ Scribed by Satoshi Fujita; Arthur M. Farley

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 871 KB
• Volume: 75
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00097-8

✦ Synopsis

Under 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 P, be the path with n vertices, and C,, be the cost of an optimal, line broadcast scheme from a terminal vertex in path E,. We show that a minimum-cost line broadcast scheme from any source vertex in P, has cost no more than C, and no less than C,, -a + 2 for any n > 2 and any time t 2 [log, nl_ We derive a closed-form expression for the minimum cost of a minimum-time