Name
Abstract | ||
|---|---|---|
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 data 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. In contrast, we present graphs where without coding the rate must be a factor Ω(log|V|) smaller. However, so far no fast algorithms for constructing appropriate coding schemes were known. Our main result are polynomial time algorithms for constructing coding schemes for multicasting at the maximal data rate. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1145/777412.777464 | SPAA |
Keywords | Field | DocType |
main result,intermediate node,coding scheme,sink node,network information flow,famous max-flow min-cut theorem,polynomial time algorithm,fast algorithm,data rate,source node,appropriate coding scheme,maximal data rate,linear algebra,coding,finite field,information flow,randomized algorithm,multicasting,communication | Linear network coding,Linear algebra,Information flow (information theory),Randomized algorithm,Finite field,Computer science,Algorithm,Coding (social sciences),Multicast,Time complexity,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-661-7 | 127 | 124.24 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Sanders | 1 | 127 | 124.24 |
| Sebastian Egner | 2 | 158 | 132.06 |
| Ludo Tolhuizen | 3 | 166 | 134.16 |