非表示:
キーワード:
-
要旨:
The famous max-flow min-cut theorem states that a source node $s$ can
send information through a network (V,E) to a sink node t at a
rate determined by the min-cut separating s and t. Recently it
has been shown that this rate can also be achieved for multicasting to
several sinks provided that the intermediate nodes are allowed to
reencode the information they receive. We give
polynomial time algorithms for solving this problem. We additionally
underline the potential benefit of coding by showing that multicasting
without coding sometimes only allows a rate that is a factor
Omega(log |V|) smaller.
