Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals)
Conference Paper
Publication Date:
2001
Short description:
Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals) / C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano. - STAMPA. - 2010:(2001), pp. 271-282. ( 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 deu 15 - 17 Febbraio 2001) [10.1007/3-540-44693-1_24].
abstract:
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.
Iris type:
Relazione in Atti di Convegno
Keywords:
Distributed Systems; Approximation algorithm; circuit-switched network
List of contributors:
C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano
Book title:
STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings
Published in: