Minimum Power Range Assignment for Symmetric
Connectivity in Sensor Networks with two Power Levels

arXiv:1605.01752v1 [cs.DS] 5 May 2016

Stefan Hoffmann and Egon Wanke
{Stefan.Hoffmann, E.Wanke}@uni-duesseldorf.de
Institute of Computer Science, Heinrich-Heine-Universität Düsseldorf
D-40225 Düsseldorf, Germany

Abstract. This paper examines the problem of assigning a transmission power to every
node of a wireless sensor network. The aim is to minimize the total power consumption while
ensuring that the resulting communication graph is connected. We focus on a restricted
version of this Range Assignment (RA) problem in which there are two different power
levels. We only consider symmetrical transmission links to allow easy integration with low
level wireless protocols that typically require bidirectional communication between two
neighboring nodes. We introduce a parameterized polynomial time approximation algorithm with a performance ratio arbitrarily close to π 2 /6. Additionally, we give an almost
linear time approximation algorithm with a tight quality bound of 7/4.

Keywords: range assignment, power consumption, radio network, sensor network, wireless ad hoc network, approximation algorithm

1

Introduction

A sensor network consists of a large number of small devices that are deployed across
a geographic area to monitor certain aspects of the environment. These sensor nodes
are able to communicate with each other through a wireless communication channel. As
a result of their size the resources of the sensor nodes are strongly limited in terms of
available energy. This leads to a very limited range of the radio transmitters.
Minimizing the power consumption to prolong the lifetime of the network has received
considerable attention, because the replacement of batteries in a large scale network is
practically difficult or even impossible.
A common approach to save energy is based on adjusting the power levels of the
sensor nodes’ radio transmitters while maintaining a connected network structure. This
Range Assignment (RA) problem is typically defined as computing a range assignment
f : P → R+ for a set of points P ⊂PRn (1 ≤ n ≤ 3), representing the nodes in
the network, such that the total energy p∈P c(f (p)) is minimal (c being a cost function
according to a radio wave propagation model) under the constraint that the graph (P, E),
E := {(p, q) ∈ P 2 | kp − qk2 ≤ f (p)} is strongly connected, where kp − qk2 denotes the
Euclidean distance between p and q. This is called the asymmetric RA problem.
Since many low level protocols for wireless communication like IEEE 802.11 require
bidirectional transmission links for hop-by-hop acknowledgements [8], the constraint of
the asymmetric RA problem is often altered to only consider bidirectional edges E ′ :=
{{p, q} | (p, q) ∈ E ∧ (q, p) ∈ E} for an undirected connected graph. This problem is
called the symmetric RA problem.

2

Contribution
This paper examines the symmetric version of the RA problem in networks with two
power levels (denoted by 2LSRA). The 2-dimensional decision version of the 2LSRA
problem is NP-complete, because the proof of [5] for the asymmetric case can easily be
modified to the symmetric case. We introduce an approximation algorithm (denoted by
Approx2LSRAk ) for the 2LSRA problem parameterized by an integer k ≥ 2. We proof
that the performance ratio of Approx2LSRAk is between
3k − 2
2k − 2

k−1

and

X 1
1
+
.
k−1
i2
i=1

Algorithm Approx2LSRAk can easily be implemented such that its running time is in
O(|V |k ), where V is the set of sensor nodes. This provides a parameterized polynomial
time approximation algorithm with a performance ratio arbitrarily close to π 2 /6. For the
case k = 3, for which Approx2LSRAk has a tight performance of 7/4, we provide an
implementation running in almost linear time.
The approximation algorithm Approx2LSRAk is based solely on the graph structure
and the following assumption: If a node u can receive messages from a node v while v
transmits with power rmin , u can still receive messages from v if v increases its power
level to rmax . Note that the algorithm requires neither any embedding of the nodes into
Rd for some dimension d nor any kind of correlation between the transmission links, as
for example, if u can receive messages from v then v can receive messages from u.
Related Work
Both versions of the RA problem are typically considered with cost function c(d) =
β · dα + γ for a distance-power gradient α ≥ 1, a transmission quality parameter β and
some γ ≥ 0. Kirousis et al. proved in [9] that the decision version of the asymmetric
RA problem is NP-hard for 3-dimensional point sets for all α ≥ 1, β = 1 and γ = 0.
They also presented a factor 2 approximation algorithm based on a minimum spanning
tree. The hardness result was extended by Clementi et al. in [6] to 2-dimensional point
sets. Clementi et al. also showed in [6] the APX-hardness of the 3-dimensional case.
This implies that there is no polynomial time approximation scheme (PTAS) for the
3-dimensional asymmetric RA problem, unless P=NP. The 1-dimensional case, on the
other hand, is solvable in time O(|P |4 ) by dynamic programming techniques, see [9].
For the symmetric RA problem, Blough et al. showed in [4] that the decision version
is also NP-hard for 2- and 3-dimensional point sets, whereas Althaus et al. have shown
in [2,1] that there is a simple approximation algorithm with approximation factor 11/6
as well as a parameterized polynomial time approximation algorithm with a performance
ratio arbitrarily close to 5/3.
Carmi and Katz introduced in [5] the additional restriction of only two different
transmission powers rmin and rmax with rmin < rmax . This simplifies the RA problems to
the question of how to determine a minimum set of sensor nodes that have to transmit
with maximum power rmax in order to obtain connectivity. They study the 2-dimensional

3

asymmetric version of this problem, proof its NP-completeness, and present an approximation algorithm with a factor of 11/6 as well as a rather theoretical approximation
algorithm with a factor of 9/5.
While formulated in an entirely different way, the 2LSRA problem is basically equivalent to the problem called Max Power Users given in [10], which was renamed to
{0, 1}-MPST by the authors of [11]. And although this work has been conducted independently of [10], the concept used for an approximation algorithm is remarkably
similar: In this paper a family of approximation algorithms, called Approx2LSRAk and
based on a positive integer k ∈ N, is developed and analyzed. The authors of [10] introduce two approximation algorithms which are in fact equivalent to our special cases
Approx2LSRA3 and Approx2LSRA4 . However, the best known approximation ratio
possibly for this problem is given in [11] where the authors prove that the algorithm
presented in [1] for the more general problem of arbitrary power levels achieves an approximation ratio of 3/2 for the special case of two power levels. It is noteworthy that
the algorithm given in [1] is based on a rather complex approximation scheme for the
classical Steiner Tree problem, while the idea used in this paper and in [10] is a simple,
fast and easy to implement greedy approach.

2

Definitions and Terminology

The problem we consider is motivated by wireless sensor networks in which the nodes have
two transmission power levels, a min-power and a max-power level. Such networks are
usually represented as directed graphs in that the directed edges represent connections
from source nodes to target nodes. Since almost all communication protocols are based on
symmetric connections, we are mainly interested in the underlying symmetric networks.
These networks can be represented by undirected graphs.
Our goal is to find a minimum number k of nodes such that if these k nodes use maxpower and the remaining nodes use min-power then the resulting underlying symmetric
network is connected.
The problem is now defined more formally. We consider undirected graphs G = (V, E),
where V is the set of nodes and E ⊆ {{u, v} | u, v ∈ V, u 6= v} is a set of undirected
edges. A graph G′ = (V ′ , E ′ ) is a subgraph of G = (V, E) if V ′ ⊆ V and E ′ ⊆ E. It is an
induced subgraph of G, denoted by G|V ′ , if E ′ = E ∩ {{u, v} | u, v ∈ V ′ }.
A path between two nodes u, v ∈ V is a sequence of nodes u1 , . . . , uk ∈ V , k ≥ 1,
such that u1 = u, {ui , ui+1 } ∈ E for i = 1, . . . , k − 1 and uk = v. Graph G = (V, E) is
connected if there is a path between every pair of nodes. A path u1 , . . . , uk , k ≥ 3, is a
cycle if {uk , u1 } ∈ E, a graph without cycles is a forest, and a connected forest is a tree.
A connected component of G is a maximal induced subgraph of G that is connected. Let
CC(G) be the set of all node sets of the connected components of G.
For a node u ∈ V , let dmin (u) ⊆ V and dmax (u) ⊆ V be the set of nodes reachable from
u with min-power or max-power, respectively. That is, dmin and dmax can be considered
as mappings from V to the power set P(V ) of V , i.e., to the set of all subsets of V .

4

Definition 1. For a node set V , a subset U ⊆ V , and two mappings dmin : V → P(V )
and dmax : V → P(V ) define the min-power edges between nodes in U as
Emin (U ) := {{u, v} | u, v ∈ U, u 6= v, u ∈ dmin (v), v ∈ dmin (u)},
the max-power edges between nodes in U as
Emax (U ) := {{u, v} | u, v ∈ U, u 6= v, u ∈ dmax (v), v ∈ dmax (u)} and
the min-max-power graph G(V, dmin , U, dmax ) := (V, Emin (V ) ∪ Emax (U )).
The min-max-power graph G(V, dmin , U, dmax ) is also denoted by G(U ) if V , dmin ,
and dmax are known from the context. We also assume that dmin (v) ⊆ dmax (v) for all
v ∈V.
The min-max-power graph G(U ) represents the underlying symmetric network for
the case that the nodes of U use max-power and the remaining nodes of V \ U use minpower. Graph G(∅) is also called the min-power graph whereas graph G(V ) is also called
the max-power graph.
The definition of the min-max-power graph is used to define the 2-Level Symmetric
Range Assignment problem as follows.

2-Level Symmetric Range Assignment (2LSRA)
Given: A node set V and two mappings dmin : V → P(V ) and dmax : V → P(V ) such that the
max-power graph G(V ) is connected.
Task: Compute a set U ⊆ V of minimum cardinality such that the min-max-power graph G(U ) is
connected.

The decision problem of finding a node set U of size at most k, for an additionally
given integer k, such that G(U ) is connected is NP-complete. This result is implicitly
contained in Theorem 6.1 of [5], which proofs the NP-completeness of the corresponding
asymmetric version.

3

An approximation algorithm for 2LSRA

If the min-max-power graph G(U ) is connected for some set U ⊆ V then U has to
contain at least one node of every connected component of the min-power graph G(∅).
That is, the number |CC(G(∅))| of connected components of G(∅) is a lower bound for
the size of such a set U . On the other hand, it is easy to find a set U ⊆ V with at most
2(|CC(G(∅))| − 1) nodes such that G(U ) is connected. Such a set can be determined by a
simple spanning tree algorithm. Let H be the graph that has a node for every connected
component of G(∅) and an edge between two nodes C, C ′ ∈ CC(G(∅)) if there are nodes

5

u ∈ C, u′ ∈ C ′ such that u′ ∈ dmax (u) and u ∈ dmax (u′ ). Let T be a spanning tree for H.
Then for every edge {C, C ′ } of T we can select two nodes u ∈ C, v ∈ C ′ from different
connected components of G(∅) such that for the set U of all these selected nodes the
min-max-power graph G(U ) is connected.
Observation 1 Any solution for an instance of 2LSRA contains at least
|CC(G(∅))| and at most 2(|CC(G(∅))| − 1) nodes.
Our algorithm starts with the min-power graph (V, E0 ) := G(∅) and an empty node
set U0 that is successively extended to node sets Ui by adding node sets Mi such that
(V, Ei ) has less connected components than (V, Ei−1 ), where Ei := Ei−1 ∪ Emax (Mi ).
This is done until (V, Ei ) is connected, which implies that G(Ui ) is connected, because
(V, Ei ) is a subgraph of G(Ui ). Obviously, a good choice for Mi is a set for which the
ratio
|CC((V, Ei−1 ))| − |CC((V, Ei ))|
|Mi |
is high. For example, if each Mi consists of two nodes then the number of connected components will be reduced by one at each extension and the algorithm computes a solution
of size at most 2(|CC(G(∅))| − 1). This is equivalent to a spanning tree solution. If each
Mi consists of three nodes and the number of connected components is reduced by two at
each extension, then the algorithm computes a solution of size at most 32 (|CC(G(∅))|−1).
Definition 2. A set of nodes M ⊆ V of cardinality k is called a k-merging for a graph
G = (V, E) and a mapping dmax : V → P(V ), if
1. the graph (M, Emax (M )) is connected, and
2. the k nodes of M are in k different connected components of G.
If we add a k-merging Mi to node set Ui−1 then Ui = Ui−1 ∪ Mi and
|CC((V, Ei−1 ))| − |CC((V, Ei ))|
k−1
=
.
|Mi |
k
The approximation algorithm Approx2LSRAk shown in Figure 1 has a fixed parameter k ≥ 2. Starting with k′ = k, it successively gathers k′ -mergings as long as possible.
After this it decreases k′ and proceeds in the same way until (V, Ei ) is connected, which
will occur at the latest during the iteration for k′ = 2, where all remaining 2-mergings
are considered.
Observation 2 Algorithm Approx2LSRAk always finds a solution for an instance
V, dmin , dmax of 2LSRA.
For every integer k ∈ N the algorithm Approx2LSRAk listed in Figure 1 can be
implemented such that its running time is in O(|V |k ), because the running time is dominated by the computation of all subsets M ⊆ V with |M | = k in line 7. Therefore we
get a polynomial time algorithm for every constant integer k.

6
1: function Approx2LSRAk (V, dmin , dmax )
2:
k′ ← k
3:
i←0
4:
U0 ← ∅
5:
E0 ← Emin (V )
6:
while (V, Ei ) is not connected do
7:
while there is a k′ -merging Mi ⊆ V for (V, Ei ) do
8:
Ui+1 ← Ui ∪ Mi
9:
Ei+1 ← Ei ∪ Emax (Mi )
10:
i←i+1
11:
end while
12:
k′ ← k′ − 1
13:
end while
14:
return Ui
15: end function
Fig. 1. Algorithm Approx2LSRAk for a fixed integer k ≥ 2

4

Upper Bounds on the quality of Approx2LSRAk

Let UOP T (I) be an optimal solution for an instance I = (V, dmin , dmax ) of 2LSRA. We
show that Approx2LSRAk for a positive integer k ≥ 2 computes a solution Uk (I) such
that
k−1
X
|Uk (I)|
1
1
≤
+
.
|UOP T (I)|
k−1
i2
i=1

Lemma 1. Let F0 = (V, E0 ) be a forest with n = |V | nodes and m = |E0 | edges and let
p ∈ N, 1 ≤ p ≤ n − 1 and l ∈ N be positive integers.
Furthermore let Fi = (V, Ei ), 1 ≤ i ≤ l, be a sequence of forests such that Fl contains
only trees with less than p edges and Ei ⊆ Ei−1 , |Ei | = |Ei−1 | − p.
then
If m > n·(p−1)
p
1. F0 contains a tree with at least p edges,
2. each forest Fi ,


n · (p − 1)
1
· m−
,
i <
p
p
3.

contains a tree with at least p edges and

 
n · (p − 1)
1
· m−
.
l ≥
p
p

Proof.
1. Forest F0 consists of n − m trees. If m > (n − m) · (p − 1), then at least one of these
n − m trees has more than p − 1 edges and thus at least p edges.
m > (n − m) · (p − 1)

⇔

m>

n · (p − 1)
p

7

2. Forest Fi has m − i · p edges. If


n · (p − 1)
1
i< · m−
p
p


then Fi has more than m − p1 · m − n·(p−1)
edges and by Lemma 1.1.
· p = n·(p−1)
p
p
at least one tree with p edges.
3. Follows from 2. and the fact that we still can remove at least p more edges if there is
a tree with p edges.
⊔
⊓
Lemma 2. Let k ∈ N, k ≥ 3 be a positive integer and UOPT an optimal solution for an
instance of 2LSRA. Then Approx2LSRAk always finds at least



1
|UOPT | · (k − 2)
· (|CC(G(∅))| − 1) −
k−1
k−1
k-mergings.
Proof. Let M0 , . . . , Ml−1 be the k-mergings chosen by Approx2LSRAk in Line 7 for a
given instance V, dmin , dmax of 2LSRA and E1 , . . . , El the edge sets computed in line 9
starting with edge set E0 of the min-power graph G(∅).
Let H = (CC(G(∅)), EH ) be the undirected graph that has a node for every connected
component of G(∅) and an edge {C1 , C2 } if and only if there is an edge {u, v} in the
min-max-power graph G(UOPT ) with u ∈ C1 and v ∈ C2 .
For i = 0, . . . , l we define a tree Ti and a forest Fi = (UOPT , Ei′ ) that satisfies the
following invariant:
(I1) The node set R of every tree of forest Fi , 0 ≤ i ≤ l, is a |R|-merging for graph
(V, Ei ).
Let T0 = (CC(G(∅)), ET ) be a spanning tree of H and F0 be a forest that contains for
every edge {C1 , C2 } ∈ ET exactly one edge {u, v} of G(UOPT ) with u ∈ C1 and v ∈ C2 .
Invariant (I1) above obviously holds true for F0 .
For every k-merging Mi = {u1 , . . . , uk }, 0 ≤ i < l, we successively define trees
Ti,1 , . . . , Ti,k and forests Fi,1 , . . . , Fi,k starting with Ti,1 := Ti and Fi,1 := Fi such that
Ti+1 := Ti,k and Fi+1 := Fi,k .
For j = 2, . . . , k, tree Ti,j and forest Fi,j are defined by merging two nodes of tree
Ti,j−1 and removing one edge from forest Fi,j−1 , respectively.
Let C ∗ be the node of Ti,j−1 that contains the nodes u1 , . . . , uj−1 and let C be the
node of Ti,j−1 that contains uj . Choose any edge {C ′ , C ′′ } from the path between C ∗ and
C in Ti,j−1 , replace the two nodes C ∗ , C by one new node C ∗ ∪ C in Ti,j−1 , and remove
edge {u, v} with u ∈ C ′ and v ∈ C ′′ from Fi,j−1 .
If Invariant (I1) holds true for Fi , then it holds true for Fi+1 , because the construction
above guarantees that for every simple path v1 , . . . , vm in Fi+1 the nodes vi , 1 ≤ i ≤ m,
are in m different connected components of (V, Ei+1 ).

8

Since forest F0 has |UOPT | nodes and |CC(G(∅))| − 1 edges, by Lemma 1.3, algorithm
Approx2LSRAk finds at least





1
|UOPT | · (k − 2)
· (|CC(G(∅))| − 1) −
k−1
k−1
⊔
⊓

k mergings.

Theorem 1. Let I = (V, dmin , dmax ) be an instance of 2LSRA and UOP T (I) an optimal
solution. For a fixed integer k ≥ 2, algorithm Approx2LSRAk computes a solution
Uk (I) such that
|Uk (I)|
|UOP T (I)|

k−1

≤

X 1
1
+
.
k−1
i2
i=1

Proof. Let li , 3 ≤ i ≤ k, denote the number of i-mergings chosen by Approx2LSRAk .
Furthermore, let ck := |CC(G(∅))| be the number of connected components of the minpower graph and let ci , 2 ≤ i ≤ k − 1, be the number of connected components before
Approx2LSRAk searches for i-mergings for the first time, that is ci := |CC((V, Es(i) ))|
P
with s(i) := kj=i+1 lj = lk + . . . + li+1 . Then we know for 3 ≤ i ≤ k that
ci−1 = ci − (i − 1)li

⇔

li =

ci − ci−1
.
i−1

(1)

Let dmin,s(i) : V → P(V ) be defined by u ∈ dmin,s(i) (v) if and only if {u, v} ∈ Es(i) for all
u, v ∈ V . Then (V, Es(i) ) is the min-power graph of instance Is(i) := (V, dmin,s(i) , dmax ).
Now we can apply Lemma 2 for k = i on instance Is(i) and get

⇔

ci − ci−1
i−1

≥

ci−1 − 1

≤



1
i−2
· |UOP T (Is(i) )|
ci − 1 −
i−1
i−1
i−2
i−2
· |UOP T (Is(i) )| ≤
· |UOP T (I)|,
i−1
i−1

(2)

9

because |UOP T (Is(i) )| ≤ |UOP T (I)|. We can derive an upper bound for |Uk (I)| as follows.
|Uk (I)|

k
X

≤

(1)

i · li + 2(c2 − 1)

=

i=3

i=3

2(ck − 1) −

=

=

=
(2)

≤

k
X

i=3
k
X

(i − 2)li

(1)

=

k
X
(i − 1)li
i · li + 2 ck − 1 −
i=3

2(ck − 1) −

k
X
i=3

i−2
(ci−1 − 1) −
i−1

k
X

!

i−2
(ci − ci−1 )
i−1

i−2
(ci − 1)
i−1
i=3
i=3

k−1 
c2 − 1 (k − 2)(ck − 1) X i − 1 i − 2
2(ck − 1) +
−
+
−
(ci − 1)
2
k−1
i
i−1
i=3


k−1
k−2
c2 − 1 X ci − 1
+
2−
· (ck − 1) +
k−1
2
i(i − 1)
i=3


k−1
k−2
|UOP T (I)| X |UOP T (I)|
+
2−
· (ck − 1) +
k−1
4
i2
2(ck − 1) +

=

k
X

i=3

Since ck − 1 < |UOP T (I)|, see Observation 1, we get
k−1

|Uk (I)| <

k−2 1 X 1
+ +
2−
k−1 4
i2
i=3

!

k−1

· |UOP T (I)| =

X 1
1
+
k−1
i2
i=1

!

· |UOP T (I)|.
⊔
⊓

Corollary 1. Approx2LSRA3 is a 7/4 factor approximation algorithm for 2LSRA.
Observation 3 The upper bound in Theorem 1 tends to π 2 /6 for k → ∞. [3]

5

Lower Bounds on the quality of Approx2LSRAk

In this section we present worst case examples for algorithm Approx2LSRAk and derive
lower bounds on its quality. For k = 3 we demonstrate that the upper bound of 7/4
obtained in section 4 is tight.
Theorem 2. Let k ∈ N, k ≥ 3 be a positive integer. For an instance I of 2LSRA let
Uk (I) be the solution computed by Approx2LSRAk and UOP T (I) an optimal solution.
For all ǫ > 0 there is an instance I such that
3k − 2
|Uk (I)|
>
− ǫ.
|UOP T (I)|
2k − 2

10

Proof. For a positive integer t ∈ N let It be the instance for 2LSRA defined as follows
(see Figure 2).
V :={(0, 0, 0)}
∪

∪

{(d, 3, 0) | 1 ≤ d ≤ t}

{(d, r, c) | 1 ≤ d ≤ t, 1 ≤ r ≤ 3, 1 ≤ c < k}

Emin (V ) :={{(0, 0, 0), (d, 3, 0)} | 1 ≤ d ≤ t}
∪ {{(d, 2, c), (d, 3, c)} | 1 ≤ d ≤ t, 1 ≤ c < k}
Emax (V ) :=Emin (V )

∪

{{(0, 0, 0), (d, 2, 1)} | 1 ≤ d ≤ t}

∪

{{(d, r, c), (d, r, c + 1)} | 1 ≤ d ≤ t, r ∈ {2, 3}, 1 ≤ c < k − 1}

∪

{{(d, 3, 0), (d, 3, 1)} | 1 ≤ d ≤ t}

∪

{{(d, 1, c), (d, 2, c)} | 1 ≤ d ≤ t, 1 ≤ c < k}

The (unique) optimal solution for It is
UOP T (It ) = {(0, 0, 0)} ∪ {(d, r, c) | 1 ≤ d ≤ t, r ∈ {1, 2}, 1 ≤ c < k},
meaning that |UOP T (It )| = 1 + 2(k − 1)t. Algorithm Approx2LSRAk , in the worst case,
successively gathers all k-mergings {(d, 3, c) | 0 ≤ c < k} for 1 ≤ d ≤ t first, followed by
the remaining 2-mergings {(d, 1, c), (d, 2, c)} for 1 ≤ d ≤ t and 1 ≤ c < k. Thus we get
q(k, t) :=

kt + 2(k − 1)t
k + 2(k − 1)
|Uk (It )|
=
=
= 1
|UOP T (It )|
1 + 2(k − 1)t
t + 2(k − 1)

1
t

3k − 2
+ 2k − 2

and limt→∞ (q(k, t)) = 3k−2
2k−2 , which implies the existence of a positive integer tǫ ∈ N such
3k−2
⊔
⊓
that q(k, tǫ ) > 2k−2 − ǫ.
Corollary 2. The upper bound of 7/4 on the quality of Approx2LSRA3 is tight.

1,1,1

1,1,2

1,1,k−1

2,1,1

2,1,2

2,1,k−1

t,1,1

t,1,2

t,1,k−1

1,2,1

1,2,2

1,2,k−1

2,2,1

2,2,2

2,2,k−1

t,2,1

t,2,2

t,2,k−1

1,3,1

1,3,2

1,3,k−1

2,3,1

2,3,2

2,3,k−1

t,3,1

t,3,2

t,3,k−1

1,3,0

2,3,0

t,3,0

max−power edges
0,0,0

min−power edges

Fig. 2. Instance It of Theorem 2: The min-power edges Emin (V ) are drawn as thick blue lines, the maxpower edges Emax (V ) are drawn as thin black lines and the connected components of the min-power
graph G(∅) are encircled by dashed boxes.

11

6

Efficient Implementation of Approx2LSRA3

For k = 3 the algorithm can be implemented in almost linear time using a union-find
data structure D to organize the node sets of the connected components of (V, Ei ).
We assume that the mappings dmin and dmax are explicitly
P given as relations dmin ⊂
V × P(V
P ) and dmax ⊂ V × P(V ) of size smin := |V | + v∈V |dmin (v)| and smax :=
|V | + v∈V |dmax (v)|, respectively. The implementation is based on the following three
steps.
1. Initialization: Generate the set of min-power edges Emin (V ) and the set of maxpower edges Emax (V ). This can be done in time O(smin ) and O(smax ), respectively.
Afterwards D can be initialized with the connected components of G(∅) during one
iteration over the min-power edges by performing two find operations u′ = f ind(u),
v ′ = f ind(v) and one union operation union(u′ , v ′ ) for each {u, v} ∈ Emin (V ).
The total number of f ind and union operations for this step is linear in |V | and
|Emin (V )| and therefore also linear in smin .
2. Finding 3-mergings: For every node v ∈ V examine all incident edges {v, u} ∈
Emax (V ) after identifying the connected component of v via Cv = f ind(v). If Cu :=
f ind(u) 6= Cv , node u and its component Cu are temporarily saved until a second
node u′ adjacent to v is found, such that Cv 6= Cu′ and Cu 6= Cu′ . Then {v, u, u′ } is a
3-merging that is added to the solution and the three connected components Cv , Cu
and Cu′ are merged via two union operations.
Since every edge in Emax (V ) has to be considered only twice, the total number of
f ind and union operations for this step is linear in |V | and |Emax (V )| and therefore
also linear in smax .
3. Finding 2-mergings: For every edge {u, v} ∈ Emax (V ) add {u, v} to the solution and
call union(u, v), if f ind(u) 6= f ind(v). Again, the total number of f ind and union
operations for this step is linear in smax .
Theorem 3. Approx2LSRA3 can be implemented such that the running time is in
O(f (smin , smax ) · α(f (smin , smax ), |V |)) where α is the inverse Ackermann function and
f ∈ O(smin + smax ).
Proof. The total number of union and f ind operations f (smin , smax ) is linear in smin and
smax as discussed above. Tarjan and Leeuwen show in [12] that any sequence of m ∈ N
union and f ind operations on a union-find data structure saving n ∈ N elements can
be performed in time O(m · α(m, n)). Fredman and Saks show in [7] that this bound in
tight.
⊔
⊓

12

References
1. E. Althaus, G. Calinescu, I.I. Mandoiu, S. Prasad, N. Tchervenski, and A. Zelikovsky. Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks. Wirel. Netw.,
12(3):287–299, May 2006.
2. E. Althaus, G. Călinescu, I.I. Mandoiu, S.K. Prasad, N. Tchervenski, and A. Zelikovsky. Power
efficient range assignment in ad-hoc wireless networks. In WCNC, pages 1889–1894. IEEE, 2003.
3. T. Apostol. A proof that Euler missed: evaluating zeta(2) the easy way. Math. Intelligencer, 5(3):59–
60, 1983.
4. D. Blough, M. Leoncini, G. Resta, and P. Santi. On the symmetric range assignment problem in
wireless ad hoc networks. In R.A. Baeza-Yates, U. Montanari, and N. Santoro, editors, IFIP TCS,
volume 223 of IFIP Conference Proceedings, pages 71–82. Kluwer, 2002.
5. P. Carmi and M.J. Katz. Power assignment in radio networks with two power levels. Algorithmica,
47(2):183–201, 2007.
6. A. Clementi, P. Penna, and R. Silvestri. Hardness results for the power range assignment problem in packet radio networks. In Randomization, Approximation, and Combinatorial Optimization.
Algorithms and Techniques, pages 197–208. Springer, 1999.
7. M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proceedings of
the Twenty-first Annual ACM Symposium on Theory of Computing, STOC ’89, pages 345–354, New
York, NY, USA, 1989. ACM.
8. IEEE. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications
(ANSI/IEEE Std 802.11, 1999 Edition (R2003)). Institute of Electrical and Electronics Engineers,
Inc., June 2003.
9. L. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc. Power consumption in packet radio networks.
Theoretical Computer Science, 243(1-2):289–305, 2000.
10. E.L. Lloyd, R. Liu, and S.S. Ravi. Approximating the minimum number of maximum power users
in ad hoc networks. In Ioanis Nikolaidis, Michel Barbeau, and Evangelos Kranakis, editors, Ad-Hoc,
Mobile, and Wireless Networks, volume 3158 of Lecture Notes in Computer Science, pages 1–13.
Springer Berlin Heidelberg, 2004.
11. Z. Nutov and A. Yaroshevitch. Wireless network design via 3-decompositions. Information Processing
Letters, 109(19):1136 – 1140, 2009.
12. R. Tarjan and J. van Leeuwen. Worst-case analysis of set union algorithms. J. ACM, 31(2):245–281,
March 1984.

