Open AccessEfficient combination of polynomial time algorithm and subtree decomposition for network coding
Author(s) -
Liu Yantao,
Morgan Yasser
Publication year - 2015
Publication title -
iet communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.355
H-Index - 62
eISSN - 1751-8636
pISSN - 1751-8628
DOI - 10.1049/iet-com.2015.0386
Subject(s) - linear network coding , time complexity , computer science , multicast , algorithm , coding (social sciences) , computational complexity theory , theoretical computer science , mathematical optimization , mathematics , distributed computing , computer network , statistics , network packet
Aiming at the inefficiency of polynomial time algorithm of linear network coding (NC) for multicast applications, the authors propose an improved algorithm which combines polynomial time algorithm with subtree decomposition. The algorithm is composed of five steps, including line graph transforming, subtree decomposition, static subtree set generating, assigning of global coding vector, and calculation of local coding vector. Subtree decomposition decreases network scale and coding complexity steeply, so it is an efficient algorithm of linear NC for multicast. An example is given to illustrate the implementation of the algorithm. Detailed analysis to algorithm complexity and a group of numerical experiments are made to show the efficiency of the algorithm.