The minimum k-storage problem on directed graphs
| Autor: | Daniele Diodati, Cristina M. Pinotti, Alfredo Navarra, Gianlorenzo D'Angelo |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Optimal algorithms
General Computer Science Storage Problem Wireless sensor networks Storage placement Optimal algorithms Dynamic programming Directed graph Dynamic programming Directed acyclic graph Wireless sensor networks Theoretical Computer Science Storage placement Combinatorics Path length Sink (computing) Time complexity Wireless sensor network Mathematics |
| Zdroj: | Theoretical Computer Science. 596:102-108 |
| ISSN: | 0304-3975 |
| Popis: | 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 = 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 ? { k n 2 , k 2 P } ) 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 ( k n 2 ( max ? { k , d } ) d - 1 ) time, where d is the maximum out-degree of the tree 8. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect