Finding Minimum Cost Data Collection Tree with Aggregation
研究了在二维平面节点间距离为欧几里得范数平方时，构建最小成本数据聚合树的问题，证明了该问题在一般度量下是NP难的，并基于Dijkstra最便宜路径树等概念提出了近似算法。
Abstract In this paper we consider a special case of building a minimum cost data aggregation tree problem raised in the context of wireless sensor networks, when the sensors correspond to the nodes in the two-dimensional plane, and the distances between nodes are measured according to the (squared) Euclidean norm. We show that the problem is NP-hard for the general metric case and provide a number of approximation algorithms for this problem based on the concept of Dijkstra’s cheapest paths tree, Bounded-Hop Diameter Tree and Hamiltonian Cycle construction.