图形的中心 [英] Center of a graph

问题描述

给定一棵无重量边的无方向树，有 N 个顶点和 N-1 条边以及 K 个节点，找到 K 个节点，以便树中的每个节点都在 K 个节点中至少一个的 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.

我尝试解决这个问题，但是，我觉得我假设的解决方案不是很快.我的解决方案:设置 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屋！