Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals)

In this paper we study the k-station placement problem (k-SP problem for short) on graphs. This problem has application toefficient multicasting in circuit-switched networks and to spaceefficient traversals. We show that the problem is NP-complete evenfor 3-stage graphs and give an approximation algorithm with logarithmic approximation ratio. Moreover we show that the problem can be solved in polynomial time for trees.We also present algorithms for a generalized version and variants of the k-SP problem.