On the Construction of a Maximum-Lifetime Data Gathering Tree in Sensor Networks: NP-Completeness and Approximation Algorithm (Wu, Fahmy, Shroff 2008)

Data aggregation (often called data fusion) is very important in sensor networks in order to gather data from sensors as long as possible.

Wu et al. considers aggregation functions, where (several) packets of size B can be aggregated into one packet of size B, this holds for various functions such as MAX, MIN, AVG, etc. (Mitchell's book describes various models and more complicated data fusion very well)
Therefore, in a (rooted) aggregation tree, any node waits for and receives all values from its children, aggregates it with its own value, and sends the new aggregate to its parent node. Each node sends one packet to its parent and receives one packet from each of its children. If all nodes have the same life-time (a reasonable assumption), the maximum number of children should be minimized (possibly while maintaining a small height of the tree). However, the problem of computing the spanning tree with smallest maximum degree is NP hard. Wu et al. reuses ideas from Furer and Raghavachari (1994)'s algorithm for Steiner trees. (If the Steiner version is considered, only vertices from a distinguished set have to be covered.) Step by step, the algorithm tries to improve the situation for bottleneck nodes (nodes with high degree) without worsening the situation for nodes almost being bottlenecks as follows: iterate through edges and add an edge {u,v} if both u and v are neither bottleneck nor endangered and if within the cycle that appears when adding the edge there is a bottleneck node w, which will then benefit by removing one if its adjacent edges (otherwise, w is said to be blocked by u and v).

This paper is going to be presented at this year's INFOCOM in April (I found it while googling maximum lifetime data aggregation).