STATION PLACEMENT IN NETWORKS
Abstract
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
- Networks 9, 313 (1979). Crossref, ISI, Google Scholar
- Discrete Math. 25, 189 (1979). Crossref, ISI, Google Scholar
- IEEE Software 2, 49 (1985). Crossref, ISI, Google Scholar
- Networks 18, 319 (1986). Crossref, ISI, Google Scholar
- Networks 10, 59 (1980). Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 9(8), 788 (1998). Crossref, ISI, Google 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
- SIAM J. on Computing 20, 423 (1991). Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 7, 246 (1996). Crossref, ISI, Google Scholar
- C. Laforest, Gossip in Trees under Line-Communication Mode, Proc. Euro-Par '96, LNCS 1123 (1996), 333-340 . Google Scholar
- Discrete Applied Math 93, 265 (1999). Crossref, ISI, Google Scholar
- Journal of Algorithms 33, 73 (1999). Crossref, ISI, Google Scholar


