Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding

Fang Zhao, Muriel Médard, Desmond Lun, Asuman Ozdaglar

Research output: Chapter in Book/Report/Conference proceedingChapter

6 Scopus citations


Network coding, introduced by Ahlswede et al. in their pioneering work [1], has generated considerable research interest in recent years, and numerous subsequent papers, e.g., [2-6], have built upon this concept. One of the main advantages of network coding over traditional routed networks is in the area of multicast, where common information is transmitted from a source node to a set of terminal nodes. Ahlswede et al. showed in [1] that network coding can achieve the maximum multicast rate, which is not achievable by routing alone. When coding is used to perform multicast, the problem of establishing minimum cost multicast connection is equivalent to two effectively decoupled problems: one of determining the subgraph to code over and the other of determining the code to use over that subgraph. The latter problem has been studied extensively in [5, 7-9], and a variety of methods have been proposed, which include employing simple random linear coding at every node. Such random linear coding schemes are completely decentralized, requiring no coordination between nodes, and can operate under dynamic conditions [10]. These papers, however, all assume the availability of dedicated network resources.

Original languageEnglish (US)
Title of host publicationNew Directions in Wireless Communications Research
PublisherSpringer US
Number of pages33
ISBN (Print)9781441906724
StatePublished - 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)


Dive into the research topics of 'Minimum-cost subgraph algorithms for static and dynamic multicasts with network coding'. Together they form a unique fingerprint.

Cite this