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.
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. (Intervento presentato al convegno 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 tenutosi a deu nel 15 - 17 Febbraio 2001) [10.1007/3-540-44693-1_24].
Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals)
MONTANGERO, Manuela;
2001
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.
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris
