A Caltech Library Service

Network Coding: A Computational Perspective

Langberg, Michael and Sprintson, Alexander and Bruck, Jehoshua (2009) Network Coding: A Computational Perspective. IEEE Transactions on Information Theory, 55 (1). pp. 147-157. ISSN 0018-9448.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by performing algebraic operations on packets received over incoming links.

Item Type:Article
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© Copyright 2009 IEEE. Reprinted with permission. Manuscript received July 17, 2006; revised January 21, 2008. Current version published December 24, 2008. This work was supported in part by the Caltech Lee Center for Advanced Networking. Communicated by M. Médard, Associate Editor for Communications. Color versions of Figures 3 and 6–8 in this paper are available online at
Funding AgencyGrant Number
Lee Center for Advanced Networking ,CaltechUNSPECIFIED
Subject Keywords:Algorithms; computational perspective; encoding complexity; fractional network coding; integer network coding; multicast connections
Issue or Number:1
Record Number:CaltechAUTHORS:LANieeetit09
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13199
Deposited By: Archive Administrator
Deposited On:02 Feb 2009 18:41
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page