Deterministic network coding by matrix completion
Deterministic network coding by matrix completion
复制标题
DOI：
--
复制
发表时间：
2005-01
期刊：
影响因子：
--
通讯作者：
Nicholas J. A. Harvey;David R Karger;K. Murota
中科院分区：
文献类型：
--
作者：
Nicholas J. A. Harvey;David R Karger;K. Murota
针对一类特殊的网络信息流问题--多播问题，提出了一种新的确定性网络码构造算法。我们的算法很容易推广到多播问题的几个变种。我们的方法是基于一个新的算法的最大秩完成的混合矩阵---采取一个矩阵的条目是一个混合的数值和符号变量，并分配值的变量，以最大限度地提高矩阵的秩。我们的算法比现有的确定性算法更快，可以在一个较小的字段上操作。
We present a new deterministic algorithm to construct network codes for multicast problems, a particular class of network information ow problems. Our algorithm easily generalizes to several variants of multicast problems. Our approach is based on a new algorithm for maximum-rank completion of mixed matrices---taking a matrix whose entries are a mixture of numeric values and symbolic variables, and assigning values to the variables so as to maximize the resulting matrix rank. Our algorithm is faster than existing deterministic algorithms and can operate over a smaller field.