A Caltech Library Service

Network Coding: A Computational Perspective

Langberg, Michael and Sprintson, Alexander and Bruck, Jehoshua (2006) Network Coding: A Computational Perspective. In: 40th Annual Conference on Information Sciences and Systems. IEEE , Piscataway, NJ, pp. 877-882. ISBN 1-4244-0349-9.

Full text is not posted in this repository. Consult Related URLs below.

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 the 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 combining the packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V, E) in time O(|E|kh+|V|k^2h^2+h^4k^3(k+h)), where k is the number of destinations and h is the number of packets. This improves the best known running time of O(|E|kh+|V|k^2h^2(k+h)) of Jaggi et al. (2005) in the typical case of large communication graphs. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is bounded by O(h^3k^2). Next, we address the problem of finding a network code with the minimum number of encoding nodes in both integer and fractional coding networks. We prove that in the majority of settings this problem is NP-hard. However, we show that if h=O(1) and k=O(1) and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Langberg, Michael0000-0002-7470-0718
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2006 IEEE. Date of Current Version: 22 January 2007. Research supported in part by by the Caltech Lee Center for Advanced Networking and by NSF grants ANI-0322475 and CCF-0346991.
Funding AgencyGrant Number
Caltech Lee Center for Advanced Networking.UNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number:9528384
Record Number:CaltechAUTHORS:20110630-145653337
Persistent URL:
Official Citation:Langberg, M.; Sprintson, A.; Bruck, J.; , "Network Coding: A Computational Perspective," Information Sciences and Systems, 2006 40th Annual Conference on , vol., no., pp.877-882, 22-24 March 2006 doi: 10.1109/CISS.2006.286590 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:24287
Deposited By: Ruth Sustaita
Deposited On:05 Jul 2011 15:37
Last Modified:09 Nov 2021 16:22

Repository Staff Only: item control page