Polynomial Time Algorithms for Multicast Network Code Construction
Top Cited Papers
- 31 May 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 51 (6) , 1973-1982
- https://doi.org/10.1109/tit.2005.847712
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 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 re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.Keywords
This publication has 15 references indexed in Scilit:
- Polynomial Time Algorithms for Multicast Network Code ConstructionIEEE Transactions on Information Theory, 2005
- Analysis of network error correction based on network codingIEE Proceedings - Communications, 2005
- An algebraic approach to network codingIEEE/ACM Transactions on Networking, 2003
- Low complexity algebraic multicast network codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Network information flowIEEE Transactions on Information Theory, 2000
- Randomized metarounding (extended abstract)Published by Association for Computing Machinery (ACM) ,2000
- Matrix multiplication via arithmetic progressionsJournal of Symbolic Computation, 1990
- A method for computing addition tables inGF(p^n)(Corresp.)IEEE Transactions on Information Theory, 1980
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975
- Minimum partition of a matroid into independent subsetsJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965