close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Minimum Routing Cost Spanning
Trees
Kun-Mao Chao (趙坤茂)
Department of Computer Science
and Information Engineering
National Taiwan University, Taiwan
E-mail: [email protected]
WWW: http://www.csie.ntu.edu.tw/~kmchao
Minimum routing cost spanning
trees
• Given a graph, find a spanning tree with
the minimum all-to-all distance
Minimize
C (T )   d T ( u , v )
u ,v
where d T ( u , v ) is the distance
(of the shortest
• NP-hard
path)
between u and v on T
2
Routing cost C(T)=192
v1
v2
10
5
v3
3
v4
1
v5
3
Routing load l(T,e)
C (T ) 
 l (T , e ) w ( e )
e E ( T )
4
Routing cost C(T)=192
v1
v2
10
5
v3
3
l (T , ( v1 , v 2 ))  2  2  3  12
v4
1
v5
l (T , ( v1 , v 3 ))  2  1  4  8
l (T , ( v 2 , v 4 ))  2  1  4  8
l (T , ( v 2 , v 5 ))  2  1  4  8
C (T )  12  10  8  5  8  3  8  1  192
5
The impact of the topology
5
v1
5
vn
...
5
5
5
5
v3
v1
v2
1
v3
vn
...
1
1
v2
T1
C (T1 )  10 ( n  1)
T2
2
C (T 2 ) 
 2i(n  i)
1 i  n 1

n ( n  1)( n  1)
3
6
bound on routing load
x
n-x
Routing load  2 x ( n  x )
 2 nx  2 x
2
where x is an integer in [1, n  1].
Maximum

1
n
2
2
Minimum
 2 ( n  1)
7
bound on routing load
>=δn
>=δn
Routing load  2  n ( n   n )
Why?
8
Median
• Let r be the median of graph G=(V,E,W),
i.e., the vertex with the minimum total
distance to all vertices.
• In other words, r minimizes the function
f (v )   d G (v, u )
uv
where d G ( v , u ) is the shortest - path length
(distance)
between
v and u on G .
9
A 2-approximation
• A shortest-paths tree rooted at the median
of a graph is a 2-approximation of an
MRCT of the graph.
(Please refer to our discussions in class.
A note on this has been posted in our
course website.)
10
Centroid
r1
r
(a)
r2
(b)
11
Some interesting vertices
• Centroid
• Median
• Center
* a tree with positive edge lengths, the
median coincides with the centroid.
(Show that if the median is not a centroid,
a neighbor of the median will have a
smaller total distance to all vertices.)
12
1/2, 1/3, 1/4-separators
v4
v2
v1
v3
v4
v2
v5
v2
v1
v5
(c)
v3
v5
(a)
v4
v1
(b)
v3
v4
v2
v1
v3
v5
(d)
13
A δ-separator
<=kn
i
S
B1
VB(T,S,i)
<=kn
<=kn
B2
B3
brn(T,S,i)={B1,B2,B3}
<=kn
<=kn
<=kn
<=kn
<=kn
14
A 15/8-approximation algorithm
• Use a minimal 1/3-separator to estimate a
lower of the routing cost of an MRCT
– There exists a path P which is a minimal 1/3separator
2
–
4n
4n
C ( MRCT ) 
w(P )
 d MRCT ( v , P ) 
3 vV
9
• The endpoints of P are useful in
constructing a lower routing cost spanning
tree
15
A 3/2-approximation algorithm
• Besides the two endpoints of P, a centroid
is used to lower the upper bound.
16
An MST with large routing cost
1
1
2
1
2
1
2
2
2
1
......
2
17
A small routing cost tree with large
weight
1
v-1
1
v0
1
v1
1
v-2
v2
1
1
....
....
v3
....
1
1
vi
w ( v i , v i 1 )  1
w ( v 0 , v i )  (| i |  2 ) / 3
18
1/--страниц
Пожаловаться на содержимое документа