Unicast
Tight analysis of routing with 1 constraint:
Last time: O (D · |V|2) time for dynamic programming
gd (v) = min g(v’) + c(v, v’)
d-d(v,v’)
(v,v’) Î E
overestimate for sparse graphs (most graphs are sparse)
Ù
Consider particular d
v = {v1, v2, …}
Ù Ù
g d (v1) , g d (v2) …
# of neighbors of v2
time to compute #
of neighbors v1
Ù Ù
total time to compute g d (v1) , g d (v2) …
= # of neighbors of v1
+ # of neighbors of v2
+ …
+ # of neighbors of v|v|
= 2 · |E|
so, running time is D· 2 · |E| = O (D |E|) (tight analysis)
still not good enough because of D
Approximation Algorithm:
Find a path of delay at most D s.t. its cost is at most (1 + e) · optimal cost
E.g.
e = ½ , optimal solution is a path with delay <= D and cost 80
Approximation Algorithm will return a path with delay <= D and with
cost <= 80 · (1 + e) = 120
Running time: O (|V|·|E| / e)
Set e = 0.1 O (|V|·|E|· .10) = O (|V|·|E|)
Running time becomes totally dependant on the size of the graph.
Multicast
Given a network, certain nodes are multicast nodes M Í V
Find a “cheap” way of connecting these nodes.
= multicast nodes. All multicast nodes are connected in a tree. Find min-cost such tree
Theorem: finding the minimum cost multicast tree is NP-complete
Steiner tree:
(network)
Simple Heuristic:
G = (V, E) , M
Find MST over G
prune to
prune all leaves which are not in M until no such leaves are left
Running time:
construct MST: |E| · log |V|
pruning: linear
O (|E| LOG |V|) time //total cost big over estimate
Different Variant:
Shortest path tree, same procedure
This give an |E| approximation
O(|E| log |V|)