特殊圈上的逆1-maxian问题

Inverse 1-maxian problem on special cycles

逆1-maxian问题主要研究如何在一定的预算下修改网络中边的长度,使得其他所有顶点到预先给定顶点的距离之和尽可能的大.研究了特殊4-圈上的逆1-maxian问题,得到了该问题在任意预算下的最优解.然后,将问题推广到特殊n-圈的情形.最后,得到Hamming距离下特殊n-圈情形的一个最优解.

The inverse 1-maxian problem modifies the length of edges in a network under some given budget such that the sum of the distance from the other vertices to the prespecified vertex became as big as possible. We considered the inverse 1-maxian problem on the special 4-cycle and obtained the optimal solution under any budget. We then extended the problem to the special n-cycle case. Finally, we obtain an optimal solution of special n-cycle case under the Hamming distance.