0

我正在寻找一种算法来计算以领导处理器为根的图的 BFS 树r异步分布式模型中的领导处理器为根的图的 BFS 树。

唯一的要求是O(D)时间复杂度，其中D表示图的直径（与消息复杂度无关）。

目前，我正在使用 Bellman-Ford 算法，但我不知道如何保证该方法在O(D)及时。我试图使用会聚广播技术，但没有成功。

是否可以保证 Bellman-FordO(D)及时终止，或者是否有任何其他算法可以及时计算 BFS 树O(D)？

4

1 回答 1

1

是的，为同步系统设计一种高效的算法，并与 Awerbuch 的高效 Alpha 同步器 (1985) 组合，该同步器模拟同步系统。

于 2013-09-02T21:35:06.607 回答