Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals)

摘要

In this paper we study the k-station placement problem (k-SP problem, in short) on graphs. This problem has application to efficient multicasting in circuit-switched networks and to space efficient traversals. We show that the problem is NP-complete even for 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.