Fast algorithm for multicast and data gathering in wireless networks

Given a wireless network G=(V,E), we consider a maximum critical energy problem [J. Park, S. Sahni, Maximum lifetime broadcasting in wireless networks, IEEE Transactions on Computers 54 (9) (2005) 1081–1090] that has an objective of increasing the chances of doing a sequence of broadcasts. We present an optimal generalized solution algorithm running in improved optimal O(|V|+|E|) time, where V stands for a set of nodes and E stands for a set of links in the network. Our approach is applicable in an omnidirectional antenna model and can be used to solve the problem of multicasting traffic so as to maximize the lifetime of the network [A. Orda, B.-A. Yassour, Maximum-lifetime routing algorithms for networks with omnidirectional and directional antennas, in: Proc. ACM MOBIHOC, 2005] and a data gathering problem [K. Kalpakis, K. Dasgupta, P. Namjoshi, Maximum lifetime data gathering and aggregation in wireless sensor networks, Computer Networks 42 (2003) 697–716; Y. Xue, Y. Cui, K. Nahrstedt, Maximizing lifetime for data aggregation in wireless sensor networks, ACM Moble Networks and Applications 10 (6) (2005) 853–864] with an improved running time.