In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.

Station Placement in Networks / C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano. - In: PARALLEL PROCESSING LETTERS. - ISSN 0129-6264. - STAMPA. - 15:1-2(2005), pp. 117-129. [10.1142/S0129626405002106]

Station Placement in Networks

MONTANGERO, Manuela;
2005

Abstract

In this paper we study the Station Placement problem on directed graphs, a problem that has applications to efficient multicasting in circuit-switched networks. We first argue that the problem on general directed graphs can be efficiently reduced to computing bounded depth Steiner tree on complete weighted directed graphs. Then, we concentrate on the case in which the graph is a directed tree and we give polynomial time algorithms to solve the problem and a natural variant of the problem.
2005
15
1-2
117
129
Station Placement in Networks / C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano. - In: PARALLEL PROCESSING LETTERS. - ISSN 0129-6264. - STAMPA. - 15:1-2(2005), pp. 117-129. [10.1142/S0129626405002106]
C., Galdi; C., Kaklamanis; Montangero, Manuela; P., Persiano
File in questo prodotto:
File Dimensione Formato  
stationPlacement.pdf

Accesso riservato

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 861.63 kB
Formato Adobe PDF
861.63 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/455365
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact