Database Reference
In-Depth Information
l
4
l
1
l
6
Root
w4
w5
w6
w1
G
F
w2
l
1
N1
N2
w3
l
3
l
2
l
3
N3
N4
N5
N6
l
2
H
l
7
l
4
l
5
l
6
N7
N8
N9
N10
N11
N12
N13
N14
l
5
l
7
F
G
H
(a) A graph partition.
(b) A hierarchical partition tree.
Fig. 8.7
A hierarchical partition of a graph.
For each leaf node
N
L
representing a vertex
v
and its parent node
N
with as-
sociated set of vertices
V
N
, we first compute the shortest edge path between
v
and
each border vertex of
V
N
. The number of edges is stored in leaf node
N
L
. Then, we
compute a weight that stochastically dominates all weights in
V
N
, and store it as the
“optimal weight” of the node.
For an intermediate node
N
and each of its ancestor nodes
N
A
, let
V
A
be the set of
vertices associated with
N
A
. We first compute the shortest edge paths between each
border vertex of
V
N
and each border vertex of
V
A
. The number of edges in the path is
stored in
N
. Second, we compute a weight that stochastically dominates all weights
of the edges between the border vertices in
V
N
and
V
A
. It is stored as the “optimal
weight” of the node.
Therefore, the stochastic estimates can be approximated by slightly changing the
three steps in Section 8.2.2.3 as follows. In the first step, in order to find the smallest
number of edges from a vertex
v
i
to
v
, we compute the lower bound of the least
number of edges, as illustrated in Figure 8.7. Second, instead of finding an edge
weight that stochastically dominates all edges in
P
2
, we use the optimal weights
stored in nodes. The third step remains the same. In this way, we can compute a path
that has a smaller number of edges and weights that dominate all weights in
P
opt
.
8.4 Experimental Results
In this section, we report a systematic empirical study. All experiments were con-
ducted on a PC computer with a 3.0 GHz Pentium 4 CPU, 1
0 GB main memory, and
a 160 GB hard disk, running the Microsoft Windows XP Professional Edition op-
erating system, Our algorithms were implemented in Microsoft Visual Studio 2005.
The graph partition algorithm in METIS 4.0.1
1
.
and Dijkstra's Shortest Path Algo-
rithm in the Boost C++ Libraries
2
were used in the implementation of HP-trees.
1
http://glaros.dtc.umn.edu/gkhome/views/metis
2
http://www.boost.org/
