...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
【24h】

Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability

机译：布尔网络的归约和不动点与线性网络的编码可解性

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Linear network coding transmits data through networks by letting the intermediate nodes combine the messages they receive and forward the combinations toward their destinations. The solvability problem asks whether the demands of all the destinations can be simultaneously satisfied by using linear network coding. The guessing number approach converts this problem into determining the number of fixed points of coding functions over a finite alphabet (usually referred to as Boolean networks if ) with a given interaction graph that describes which local functions depend on which variables. In this paper, we generalize the so-called reduction of coding functions in order to eliminate variables. We then determine the maximum number of fixed points of a fully reduced coding function, whose interaction graph has a loop on every vertex. Since the reduction preserves the number of fixed points, we then apply these ideas and results to obtain four main results on the linear network coding solvability problem. First, we prove that non-decreasing coding functions cannot solve any more instances than routing already does. Second, we show that the triangle-free undirected graphs are linearly solvable if and only if they are solvable by routing. This is the first classification result for the linear network coding solvability problem. Third, we exhibit a new class of non-linearly solvable graphs. Fourth, we determine large classes of strictly linearly solvable graphs.
机译：线性网络编码通过让中间节点组合它们接收的消息并将组合转发到目的地来通过网络传输数据。可解决性问题询问通过使用线性网络编码是否可以同时满足所有目的地的需求。猜测数方法将这个问题转换为确定一个有限字母（通常称为布尔网络，如果具有）的编码函数固定点的数量，该给定交互图描述了哪些局部函数取决于哪些变量。在本文中，我们概括了所谓的编码函数归约，以消除变量。然后，我们确定完全简化的编码函数的最大固定点数，该函数的交互图在每个顶点上都有一个循环。由于减少保留了不动点的数量，因此我们将这些思想和结果应用于线性网络编码可解性问题的四个主要结果。首先，我们证明非递减编码功能不能解决比路由已经解决的更多实例。第二，我们证明无三角形无向图是且仅当通过路由可解时才是线性可解的。这是线性网络编码可解性问题的第一个分类结果。第三，我们展示了一类新的非线性可解图。第四，我们确定严格线性可解图的大类。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号