Đăng nhập
 
Tìm kiếm nâng cao
 
Tên bài báo
Tác giả
Năm xuất bản
Tóm tắt
Lĩnh vực
Phân loại
Số tạp chí
 

Bản tin định kỳ
Báo cáo thường niên
Tạp chí khoa học ĐHCT
Tạp chí tiếng anh ĐHCT
Tạp chí trong nước
Tạp chí quốc tế
Kỷ yếu HN trong nước
Kỷ yếu HN quốc tế
Book chapter
Tạp chí quốc tế 2017
Số tạp chí 12(2017) Trang: 3651-3664
Tạp chí: FILOMAT

We consider the problem of modifying the edge lengths of a tree at minimum cost such that a prespecified vertex become an ordered 1-median of the perturbed tree. We call this problem the inverse ordered 1-median problem on trees. Gassner showed in 2012 that the inverse ordered 1-median problem on trees is, in general, NP-hard. We, however, address some situations, where the corresponding inverse 1-median problem is polynomially solvable. For the problem on paths with n vertices, we develop an O(n^3) algorithm based on a greedy technique. Furthermore, we prove the NP-hardness of the inverse ordered 1-median problem on star graphs and propose a quadratic algorithm that solves the inverse ordered 1-median problem on unweighted stars.

Các bài báo khác
Số tạp chí 41(2017) Trang: 1591-1607
Tạp chí: Turkish Journal of Mathematics
Số tạp chí 6(2017) Trang: 93-102
Tạp chí: International Journal of Geometry
Số tạp chí 12(2017) Trang: 70-77
Tạp chí: Applications and Applied Mathematics
Số tạp chí 5 (4)(2017) Trang: 793-803
Tạp chí: International Journal of Advanced Research
Số tạp chí 5(8)(2017) Trang: 200-207
Tạp chí: International Journal of Advanced Research
Số tạp chí 2 (3)(2017) Trang: 30-48
Tạp chí: European Journal of Foreign Language Teaching
Số tạp chí 02(2017) Trang: 84-90
Tạp chí: International Journal of Advanced Scientific Research and Management


Vietnamese | English






 
 
Vui lòng chờ...