algorithm - 图的中心

Question

给定一棵无向树，该树具有带 N 个顶点和 N-1 条边的无重边以及数量 K 找到 K 个节点，使得树中的每个节点都在 K 个节点中至少一个节点的 S 距离内。此外，S 必须是可能的最小 S，因此如果 S' < S，则至少有一个节点在 S' 步骤中不可到达。

我尝试解决这个问题，但是，我觉得我假设的解决方案不是很快。我的解决方案:设定 x=1找到与每个节点 x 距离的节点让在其距离内拥有最多节点的节点成为 K 个节点之一。为每个节点重新计算，同时不计算已经覆盖的节点。这样做直到我找到 K 个 K 节点。然后，如果每个节点都被覆盖，我们就完成了，否则增加 x。

Answer 1

这个问题叫做 p-center，你可以在网上找到几篇关于它的论文，比如 this .它对于一般图确实是 NP，但在树上是多项式，无论是加权的还是未加权的。