We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of battery power. Packets are considered as integral units and not splittable. The problem is to find the maximum data flow in the sensor network subject to the energy constraint of the sensors. We show that this integral version of the problem is strongly NP-complete and in fact APX-hard. It follows that the problem is unlikely to have a polynomial time approximation scheme. Even when restricted to graphs with concrete geometrically defined connectivity and transmission costs, the problem is still strongly NP-complete. We provide some interesting polynomial time algorithms that give good approximations for the general case nonetheless. For networks of bounded treewidth greater than two, we show that the problem is weakly NP-complete and provide pseudo-polynomial time algorithms. For a special case of graphs with treewidth two, we give a polynomial time algorithm.
%0 Book Section
%1 Bodlaender:MaxFlowEnergyConstraint
%A Bodlaender, Hans
%A Tan, Richard
%A van Dijk, Thomas C.
%A van Leeuwen, Jan
%B Algorithm Theory - SWAT 2008
%D 2008
%E Gudmundsson, Joachim
%I Springer Berlin / Heidelberg
%K myown
%P 102-113
%T Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint
%U http://dx.doi.org/10.1007/978-3-540-69903-3_11
%V 5124
%X We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of battery power. Packets are considered as integral units and not splittable. The problem is to find the maximum data flow in the sensor network subject to the energy constraint of the sensors. We show that this integral version of the problem is strongly NP-complete and in fact APX-hard. It follows that the problem is unlikely to have a polynomial time approximation scheme. Even when restricted to graphs with concrete geometrically defined connectivity and transmission costs, the problem is still strongly NP-complete. We provide some interesting polynomial time algorithms that give good approximations for the general case nonetheless. For networks of bounded treewidth greater than two, we show that the problem is weakly NP-complete and provide pseudo-polynomial time algorithms. For a special case of graphs with treewidth two, we give a polynomial time algorithm.
@incollection{Bodlaender:MaxFlowEnergyConstraint,
abstract = {We study the integer maximum flow problem on wireless sensor networks with energy constraint. In this problem, sensor nodes gather data and then relay them to a base station, before they run out of battery power. Packets are considered as integral units and not splittable. The problem is to find the maximum data flow in the sensor network subject to the energy constraint of the sensors. We show that this integral version of the problem is strongly NP-complete and in fact APX-hard. It follows that the problem is unlikely to have a polynomial time approximation scheme. Even when restricted to graphs with concrete geometrically defined connectivity and transmission costs, the problem is still strongly NP-complete. We provide some interesting polynomial time algorithms that give good approximations for the general case nonetheless. For networks of bounded treewidth greater than two, we show that the problem is weakly NP-complete and provide pseudo-polynomial time algorithms. For a special case of graphs with treewidth two, we give a polynomial time algorithm.},
added-at = {2014-10-14T13:45:51.000+0200},
affiliation = {Utrecht University Department of Information and Computing Sciences Utrecht The Netherlands},
author = {Bodlaender, Hans and Tan, Richard and van Dijk, Thomas C. and van Leeuwen, Jan},
biburl = {https://www.bibsonomy.org/bibtex/2ebe3cd2d1ed0c6ed0c4fecd05aecdbe3/thomasd},
booktitle = {Algorithm Theory - SWAT 2008},
editor = {Gudmundsson, Joachim},
interhash = {8b2b63dd58e863159266243374c8c376},
intrahash = {ebe3cd2d1ed0c6ed0c4fecd05aecdbe3},
keywords = {myown},
pages = {102-113},
publisher = {Springer Berlin / Heidelberg},
series = {Lecture Notes in Computer Science},
timestamp = {2014-10-16T15:06:21.000+0200},
title = {Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint},
url = {http://dx.doi.org/10.1007/978-3-540-69903-3_11},
volume = 5124,
year = 2008
}