2005 · 41 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsComputer NetworksWireless CommunicationsAd Hoc Mobile NetworksApproximation AlgorithmsCombinatorial OptimizationGraph AlgorithmsMobile Ad Hoc NetworksWireless NetworksAd Hoc NetworkingAd Hoc Networks
The problem min-power k-connectivity seeks a power assignment to the nodes in a given wireless ad hoc network such that the produced network topology is k-connected and the total power is the lowest. In this paper, we present several approximation algorithms for this problem. Specifically, we propose a 3k-approximation algorithm for any k /spl ges/ 3, a (k + 12H (k))-approximation algorithm for k(2k - 1) /spl les/ n where n is the network size, a (k + 2 [(k + 1)/2])-approximation algorithm for 2 /spl les/ k /spl les/ 7, a 6-approximation algorithm for k = 3, and a 9-approximation algorithm for k = 4.
9
Avram Zehavi, Alon Itai · Journal of Graph Theory · 1989 · 131 citations
An application of submodular flows
András Frank, Éva Tardos · Linear Algebra and its Applications · 1989 · 126 citations