• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Views in a Graph: To Which Depth Must Equality Be Checked?
【24h】

Views in a Graph: To Which Depth Must Equality Be Checked?

机译：图形中的视图：必须检查相等的深度？

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

摘要

The view of depth $k$ of a node is a tree containing all the walks of length $k$ leaving that node. Views contain all the information that nodes could obtain by exchanging messages with their neighbors. In particular, a value can be computed by a node on a network using a distributed deterministic algorithm if and only if that value only depends on the node's view of the network. Norris has proved that if two nodes have the same view of depth $n - 1$, they have the same views for all depths. Taking the diameter $d$ into account, we prove a new bound in $O(d + d log (n/d))$ instead of $n - 1$ for bidirectional graphs with port numbering, which are natural models in distributed computation. This automatically improves various results relying on Norris's bound. We also provide a bound that is stronger for certain colored graphs and extend our results to graphs containing directed edges.
机译：节点深度$ k $的视图是一棵树，其中包含所有离开该节点的长度$ k $的游走路线。视图包含节点可以通过与邻居交换消息而获得的所有信息。特别地，当且仅当该值仅取决于该节点的网络视图时，该值才可以由网络上的节点使用分布式确定性算法来计算。诺里斯（Norris）证明，如果两个节点具有相同的深度$ n-1 $视图，则它们对所有深度都具有相同的视图。考虑到直径$ d $，我们证明了带端口编号的双向图在$ O（d + d log（n / d））$中的新界限，而不是$ n-1 $，这是分布式计算中的自然模型。依靠Norris的界线，这会自动改善各种结果。我们还为某些彩色图形提供了更强的边界，并将结果扩展到包含有向边的图形。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号