algorithm - 如何将图划分为可能重叠的部分，使得部分中包含的任何顶点与边界的距离至少为 k？

Question

如何将图划分为可能重叠的部分，以便任何顶点都包含在与边界至少距离为 k 的部分中？

问题出现在无法将整个图加载到单个机器中的情况下因为内存不够。所以另一个要求是分区有不知何故相等数量的顶点。

是否有任何算法试图最小化部件之间的公共(public)顶点？

这里的用例是这样的:您想从一个您知道需要最多 k 次遍历的初始顶点开始执行查询。包含此查询的所有顶点的部分结果为零网络利用率。因此，问题是减少这种分区的内存开销。

我应该读什么书？

我发现这个看起来很有希望: http://grafia.cs.ucsb.edu/sedge/docs/sedge-sigmod12-slides.pdf

最终编辑:谷歌决定使用哈希分区并非巧合。找到一个好的分区很困难。我也会使用散列分区并希望数据中心有良好的网络带宽。

Answer 1

您可以使用广度优先搜索从节点本身开始，获取距离相关节点仅 k 距离的所有节点。当距离原点到达k处时，可以结束搜索。

编辑:使用深度优先搜索将边界属性的最小距离分配给每个节点。完成深度优先搜索后，通过节点的简单迭代应该提供分区。例如，您可以创建一个表，将与边界的最小距离存储为键，将节点的向量存储为值，以表示分区。