Đă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í trong nước 2018
Số tạp chí 0(2018) Trang:
Tạp chí: Acta Mathematica Vietnamica

Inverse 1-center problem on a network is to modify the edge lengths or vertex weights within certain bounds so that the prespecified vertex becomes an (absolute) 1-center of the perturbed network and the modifying cost is minimized. This paper focuses on the inverse 1-center problem on a weighted tree with uniform cost of edge length modification, a generalization for the analogous problem on an unweighted tree (Alizadeh and Burkard, Discrete Appl. Math. 159, 706–716, 2011). To solve this problem, we first deal with the weighted distance reduction problem on a weighted tree. Then, the weighted distances balancing problem on two rooted trees is introduced and efficiently solved. Combining these two problems, we derive a combinatorial algorithm with complexity of O(n^2) to solve the inverse 1-center problem on a weighted tree if there exists no topology change during the edge length modification. Here, n is the number of vertices in the tree. Dropping this condition, the problem is solvable in O(n^2c) time, where c is the compressed depth of the tree. Finally, some special cases of the problem with improved  complexity, say linear time, are also discussed.

Các bài báo khác
Số tạp chí 4(2018) Trang: 21-24
Tạp chí: Tạp chí Khoa học và Công nghệ - Đại học Đà Nẵng
Số tạp chí 4 (2) - 2018(2018) Trang: 1-9
Tạp chí: Khoa học và Công nghệ Việt Nam
Số tạp chí 2(359)(2018) Trang: 56-61
Tác giả: Trần Vang Phủ
Tạp chí: Tạp chí Nhà nước và Pháp luật
Số tạp chí 56(2018) Trang: 231-236
Tác giả: Phạm Vũ Nhật
Tạp chí: Vietnam Journal of Chemistry
Số tạp chí 16(2)(2018) Trang: 123-131
Tạp chí: Tạp chí Khoa học Nông nghiệp Việt Nam (ISSN: 1859-0004)
Số tạp chí 232 tháng 5/2018(2018) Trang: 40-45
Tạp chí: . Tạp chí Khoa học kỹ thuật Chăn nuôi
Số tạp chí 10/2018(2018) Trang: 111-117
Tạp chí: Nông nghiệp và Phát triển Nông thôn
Số tạp chí 250(2018) Trang: 2-12
Tạp chí: Kinh tế và Phát triển


Vietnamese | English






 
 
Vui lòng chờ...