作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2009, Vol. 35 ›› Issue (17): 100-103. doi: 10.3969/j.issn.1000-3428.2009.17.034

• 网络与通信 • 上一篇    下一篇

基于网络数据流依赖关系的拟阵构造

贺 涛   

  1. (复旦大学计算机科学技术学院,上海 200433)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-09-05 发布日期:2009-09-05

Matroid Construction Based on Data Streams Dependent Relationship in Network

HE Tao   

  1. (School of Computer Science, Fudan University, Shanghai 200433)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-09-05 Published:2009-09-05

摘要: 将拟阵引入网络编码,从一个任意网络出发,将其在可解性等价的意义下变形成多重单播网络,对复杂的节点进行gadget替换,变形成具有统一节点形式的网络,分析各数据流间的关系,逐步找出拟阵中环和基的信息,构造一个与之对应的拟阵。从拟阵的角度分析多重单播网络的可逆性。结果表明,该拟阵可保持网络内含的数据依赖关系。

关键词: 拟阵, 多重单播网络, 网络编码

Abstract: This paper introduces matroid into network coding, transforms an arbitrary network to a multiple-unicast network which has the same solvability property, and replaces the complicated nodes in the network with a gadget, made all the nodes in the network have the same form. It analyzes the relationship of the input and output data streams of the network, constructs corresponding matroid of a network, and gets some characteristics of the network by the character of the matroid of that network. Result show that it gives more opinions about the reversibility of the multiple-unicast network.

Key words: matroid, multiple-unicast network, network coding

中图分类号: