The minimum k-storage problem on directed graphs

In standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem  . We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P=NPP=NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O(min⁡{kn2,k2P})O(min⁡{kn2,k2P}) time, where n and P are the number of nodes and the path length of the tree [7], respectively. We improve over a previous algorithm which requires O(kn2(max⁡{k,d})d−1)O(kn2(max⁡{k,d})d−1) time, where d is the maximum out-degree of the tree [8].