Geoscience Reference
In-Depth Information
(check for dominance) and enlarge this subtree until we get a Pareto location using
the criterion established in Proposition
9.1
. This procedure is then repeated for all
leaves and we end up with a subtree of all Pareto locations by using Theorem
9.9
.
Algorithm 9.7 (Solving
Q
-Criteria Median Problems on a Tree)
Input:
T
D
.V;E/
, with length function
`
and node weight vectors w
q
,
q
2
Q
.
Step 0. Set
W
WD
W.V/
Step 1. Choose a leaf
v
k
of
T
, which was not yet considered and give it the status
“considered”.
Step 2.
IF
V
Df
v
k
g
Set
X
par
.f.V//
WD
X
par
.f.T//
WDf
v
k
g
and go to Step 6
Step 3.
Let
v
l
be the only node adjacent to
v
k
IF
.
w
k
:::
w
Q
k
/
T
<
2
W
THEN
w
l
WD
w
l
C
w
k
; q
D
1;:::;Q
T
WD
T
nf
v
k
g
Step 4. IF there are any leaves left in
T
give them status “not considered”
and go to Step 1
Step 5.
X
par
.f.V//
WD
V.T/
,
X
par
.f.T//
WD
T
Set
Step 6.
STOP
X
par
.f.T//
The complexity of this algorithm is O.Q
j
V
j
/. To illustrate the algorithm consider
the following example:
X
par
.f.V//
and
Output:
Example 9.10
Consider the tree depicted in Fig.
9.24
. We solve the following
instance of a three-criteria median problem. Let l.e/
WD
1,
8
e
2
E. The weights of
the nodes are given in the following table:
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
w
1
14
6
8
4
1
2
1
3
2
2
7
w
2
11
3
3
24
5
2
2
3
2
2
5
w
3
16
2
1
1
2
3
3
1
6
4
21
0
1
0
1
50
62
60
25
31
30
@
A
and
2
W
D
@
A
.
Therefore W
D
The adjacency structure of the tree is also given in Fig.
9.24
. Now we check every
leaf till there is none left with status
“not considered”
.
