图的中心 [英] Center of a graph

问题描述

给出一个具有N个顶点和N-1个边缘的失重边缘的无方向树，并且K个数找到K个节点，这样，树中的每个节点都在K个节点中至少一个的S距离内。而且，S必须是可能的最小S，以便如果存在S’＜S。 S至少有一个节点在S的步骤中无法到达。

Given an unoriented tree with weightless edges with N vertices and N-1 edges and a number K find K nodes so that every node from a tree is within S distance of at least one of the K nodes. Also, S has to be the smallest possible S, so that if there were S' < S at least one node would be unreachable in S' steps.

我尝试解决此问题，但是，我觉得我认为的解决方案不是很快。
我的解决方案：
set x = 1
查找距每个节点x距离的节点
让距离最大的节点成为K个节点之一。
将为每个节点重新计算，而不计算已经覆盖的节点。
执行此操作，直到找到K个K节点。然后，如果每个节点都被覆盖，我们就做完了，否则增加x。

I tried solving this problem, however, I feel that my supposed solution is not very fast. My solution: set x=1 find nodes which are x distance from every node let the node which has the most nodes in its distance be one of the K nodes. recompute for every node whilst not counting already covered nodes. do this till I find K number of K nodes. Then if every node is covered we are done else increase x.

推荐答案

这个问题称为p-center，您可以找到网上有几篇关于它的论文，例如此。对于一般图形，它的确是NP，但是对于树，无论加权还是未加权，它都是多项式。

This problem is called p-center, and you can find several papers online about it such as this. It is indeed NP for general graphs, but polynomial on trees, both weighted and unweighted.

这篇关于图的中心的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！