We consider the problem of modifying edge lengths of a cycle at minimum total costs so as to make a prespecified vertex an (absolute) 1-center of the cycle with respect to the new edge legths.We call this problem the inverse 1-center problem on a cycle. To solve this problem, we first construct the so-called optimality criterion for a vertex to be a 1-center. Based on the optimality criterion, it is shown that the problem can be separated into linearly many subproblems. For a predetermined subproblem, we apply a parameterization approach to formulate it as a minimization problem of a piecewise linear convex function with a connected feasible region. Hence, it is shown that the problem can be solved in O(n2 log n) time, where n is the number of vertices in the cycle.
Tạp chí khoa học Trường Đại học Cần Thơ
Lầu 4, Nhà Điều Hành, Khu II, đường 3/2, P. Xuân Khánh, Q. Ninh Kiều, TP. Cần Thơ
Điện thoại: (0292) 3 872 157; Email: tapchidhct@ctu.edu.vn
Chương trình chạy tốt nhất trên trình duyệt IE 9+ & FF 16+, độ phân giải màn hình 1024x768 trở lên