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

Galdi, C.; Kaklamanis, C.; Montangero, Manuela; Persiano, P.

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. - LNCS 2010(2001), pp. 271-282. ((Intervento presentato al convegno STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Dresda (Germania) nel 15 - 17 Febbraio 2001.

Data di pubblicazione:	2001
Titolo:	Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals)
Autore/i:	C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano
Autore/i UNIMORE:	C. Galdi C. Kaklamanis MONTANGERO, Manuela P. Persiano mostra contributor esterni nascondi contributor esterni
Codice identificativo Scopus:	2-s2.0-84957089257
Nome del convegno:	STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science
Luogo del convegno:	Dresda (Germania)
Data del convegno:	15 - 17 Febbraio 2001
Volume:	LNCS 2010
Pagina iniziale:	271
Pagina finale:	282
Citazione:	Optimal and Approxiamte Station Placement in Networks (with Application to Multicasting and Space Efficient Traversals) / C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano. - STAMPA. - LNCS 2010(2001), pp. 271-282. ((Intervento presentato al convegno STACS 2001 18th Annual Symposium on Theoretical Aspects of Computer Science tenutosi a Dresda (Germania) nel 15 - 17 Febbraio 2001.
Tipologia	Relazione in Atti di Convegno

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11380/465768

Citazioni

I documenti presenti in Iris Unimore sono rilasciati con licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Italia, salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris