World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

STATION PLACEMENT IN NETWORKS

    In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.

    This work has been partially supported by the European RTN project ARACNE under contract HPRN-CT-1999-00112, by the European IST project CRESCCO under contract IST-2001-33135 and by the European RTN Project under contract HPRN-CT-2002-00278, COMBSTRU. A preliminary version of this paper appeared in Proc. STACS01[1].

    References

    • C. Galdi, C. Kaklamanis, M. Montangero, P. Persiano, Optimal and Approximate Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals), LNCS 2010, Proc. 18th International Symposium on Theoretical Aspects of Computer Science (STACS01), (2001), 271-282 . Google Scholar
    • A. Farley, Networks 9, 313 (1979). Crossref, ISIGoogle Scholar
    • A. Farleyet al., Discrete Math. 25, 189 (1979). Crossref, ISIGoogle Scholar
    • A. Frank, L. Wittie and A. Bernstein, IEEE Software 2, 49 (1985). Crossref, ISIGoogle Scholar
    • S. M. Hedetniemi, S. T. Hedetniemi and A. Liestman, Networks 18, 319 (1986). Crossref, ISIGoogle Scholar
    • A. Farley, Networks 10, 59 (1980). Crossref, ISIGoogle Scholar
    • J. Cohenet al., IEEE Transactions on Parallel and Distributed Systems 9(8), 788 (1998). Crossref, ISIGoogle Scholar
    • B. Awerbuch, A. Baratz and D. Peleg, Cost-Sensitive Analysis of Communication Protocols, Proc. 9th Annual ACM Symposium on Principles of Distributed Computing (PODC'90), (1990), 177-187 . Google Scholar
    • O. Wolfson and A. Segall, SIAM J. on Computing 20, 423 (1991). Crossref, ISIGoogle Scholar
    • J. G. Peters and M. Syska, IEEE Transactions on Parallel and Distributed Systems 7, 246 (1996). Crossref, ISIGoogle Scholar
    • C. Laforest, Gossip in Trees under Line-Communication Mode, Proc. Euro-Par '96, LNCS 1123 (1996), 333-340 . Google Scholar
    • G. Kortsarz and D. Peleg, Discrete Applied Math 93, 265 (1999). Crossref, ISIGoogle Scholar
    • M. Charikaret al., Journal of Algorithms 33, 73 (1999). Crossref, ISIGoogle Scholar