Geoscience Reference
In-Depth Information
IF
t
1
<t
2
THEN
Step 6.
X
par
.e/
WDf
v
i
g[f
v
j
g[
f
v
i
;v
j
g
;.t
1
;t
2
/
X
par
.e/
WDf
v
i
g[f
v
j
g
ELSE
X
par
.e/
To analyze the complexity of this algorithm, we need the following definition: A
Output:
point x
D
f
v
i
;v
j
g
;t
, t
2
Œ0;1 on one edge e
Df
v
i
;v
j
g
is called a bottleneck
point for f
q
if there exists a vertex v
k
with
w
k
>0, such that
d.v
k
;x/
D
d.v
k
;v
i
/
C
d.v
i
;x/
D
d.v
k
;v
j
/
C
d.v
j
;x/:
Let B
ij
denote the set of bottleneck points on the edge
f
v
i
;v
j
g
. Note that
j
B
ij
jj
V
j
:
If D is given, the only non constant operation in Algorithm
9.4
is the com-
putation of t
1
and t
2
.Toplotf
q
we have to determine the breakpoints of f
q
which is piecewise linear on an edge. Since these breakpoints correspond to the
bottleneck points on this edge we have to compute B
ij
for e
Df
v
i
;v
j
g
.This
can be done in O.
j
V
j
log
j
V
j
/ (see Hansen et al.
1991
). Then t
1
and t
2
can be
determined by exploring the sorted list of bottleneck points two times. The total
complexity for finding
X
par
.e/ is O.
j
V
j
log
j
V
j
/ and the total complexity for
finding
S
e2E
X
par
.e/ is O.
j
E
jj
V
j
log
j
V
j
/ (Fig.
9.17
).
Example 9.8
Consider the network in Fig.
9.17
with distance matrix
0
@
1
A
0122
1021
2201
2110
D
D
:
1
1
3
2
1
v
1
v
2
2
1
2
2
2
1
Fig. 9.17
Network of
Example
9.8
v
3
v
4
1
