algorithm - 用于并行处理的分区二叉树的 "m-bridge technique"是什么？

Question

它是如何工作的？请用英语或伪代码足够详细地解释，以便我可以用任何语言实现。

在这篇论文中提到并简要描述了: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.4.3643&rep=rep1&type=pdf

但是那里没有足够的细节来实现我自己。 (图 2b 中的权重似乎是错误的？目前还不清楚他们是如何决定在图 2c 中的何处进行切割的。)

我还查阅了原始原始论文 ( http://www-2.cs.cmu.edu/~glmiller/Publications/Papers/ReMiMo93.pdf )，但也无法从那里弄明白。

是否有更好的算法可以满足同样的需求？具体来说，任何可以保证“几乎相同大小”(但更多)的分区树？该论文建议 m-bridge 保证没有分区树大于 4n/p，如果你只有 4 个处理器，这就不能保证!

Answer 1

进行一次切割:

1. 对于树中的每个节点，计算该节点有多少后代。
2. 具有 >n/2 个后代的节点形成一条下降路径。下降到路径的底部。
3. 其中一个 child 有 n/3 到 n/2 个后代。把它从树的其余部分切下来。

要进行多次切割，请反复切割剩余的最大树。