顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.

The Obnoxious Center Problem on Tree Graphs with Subtree-Shaped Customers

The obnoxious center problem on a tree T with subtree-shaped customers asks for a location on an edge or at a vertex such that the minimum weighted distance with addend from this point to a subtree of T is as large as possible.An algorithm is given which finds the obnoxious center in O(cn +∑_(i=1)~m n_i) times where n_i is the vertex number of subtree T_i,c is the number of different subtree weights and n is the number of vertives in T.