This paper addresses the problem of optimally modifying the edge lengths such that a prespecified vertex becomes the furthest vertex from a given fixed vertex in the perturbed network. We call this problem the inverse eccentric vertex problem. We show that the problem is NP-complete even on cactus graphs. However, if the underlying graph is a cycle or a tree, we develop efficient algorithms with linear time complexity.
Tạp chí khoa học Trường Đại học Cần Thơ
Khu II, Đại học Cần Thơ, Đường 3/2, Phường Ninh Kiều, Thành phố Cần Thơ, Việt Nam
Đ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