We consider the problem of optimally placing identical resources at the nodes of a weighted tree-shaped network of size N. The resources satisfy requests issued from the nodes of the network. The cost of a placement of the resources is the sum over all nodes of the network of the product of the node weight times the distance from the closest resource. The static problem consists in determining the minimal cost placement of the resources. The dynamic version consists in recomputing such a cost when a node weight has changed.We present a linear time algorithm that computes the optimal placement of two resources in a tree. For the dynamic version we give an O(log N) time algorithm for placing one resource and, for the case of complete binary trees, an O(log N-3) time algorithm for two resources.The static algorithm is faster than the algorithms found in literature, while the dynamic algorithms are the first for this problem.

Dynamic and Static Algorithms for Optimal Placement of Resources in a Tree

Auletta V.;Parente D.;Persiano G.
1996-01-01

Abstract

We consider the problem of optimally placing identical resources at the nodes of a weighted tree-shaped network of size N. The resources satisfy requests issued from the nodes of the network. The cost of a placement of the resources is the sum over all nodes of the network of the product of the node weight times the distance from the closest resource. The static problem consists in determining the minimal cost placement of the resources. The dynamic version consists in recomputing such a cost when a node weight has changed.We present a linear time algorithm that computes the optimal placement of two resources in a tree. For the dynamic version we give an O(log N) time algorithm for placing one resource and, for the case of complete binary trees, an O(log N-3) time algorithm for two resources.The static algorithm is faster than the algorithms found in literature, while the dynamic algorithms are the first for this problem.
1996
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4894726
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 16
social impact