Mathematical Problems in Engineering
Volume 2010 (2010), Article ID 436354, 11 pages
doi:10.1155/2010/436354
Research Article

A Computational Perspective on Network Coding

Qin Guo,1,2,3 Mingxing Luo,1,2,3 Lixiang Li,1,2,3 and Yixian Yang1,2,3

1Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2Key Laboratory of Network and Information Attack and Defence Technology of MOE, Beijing University of Posts and Telecommunications, Beijing 100876, China
3National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received 10 March 2010; Revised 4 July 2010; Accepted 25 August 2010

Academic Editor: Jyh Horng Chou

Copyright © 2010 Qin Guo et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

From the perspectives of graph theory and combinatorics theory we obtain some new upper bounds on the number of encoding nodes, which can characterize the coding complexity of the network coding, both in feasible acyclic and cyclic multicast networks. In contrast to previous work, during our analysis we first investigate the simple multicast network with source rate h=2, and then h≥2. We find that for feasible acyclic multicast networks our upper bound is exactly the lower bound given by M. Langberg et al. in 2006. So the gap between their lower and upper bounds for feasible acyclic multicast networks does not exist. Based on the new upper bound, we improve the computational complexity given by M. Langberg et al. in 2009. Moreover, these results further support the feasibility of signatures for network coding.