Đă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ế 2016
Số tạp chí 1(2016) Trang:
Tạp chí: Taiwanese Journal of Mathematics

We concern the problem of modifying the edge lengths of a tree in minimum total cost so that the prespecified p vertices become the p-maxian with respect to the new edge lengths. This problem is called the inverse p-maxian problem on trees. Gassner proposed in 2008 an efficient combinatorial algorithm to solve the inverse 1-maxian problem on trees. For the case p ≥ 2, we claim that the problem can be reduced to O(p^2 ) many inverse 2-maxian problems. We then develop algorithms to solve the inverse 2-maxian problem under various objective functions. The problem under l1-norm can be formulated as a linear program and thus can be solved in polynomial time. Particularly, if the underlying tree is a star, the problem can be solved in linear time. We also develop O(n log n) algorithms to solve the problems under Chebyshev norm and bottleneck Hamming distance, where n is the number of vertices of the tree.

Các bài báo khác
Số tạp chí Volume 3, Issue 10(2016) Trang: e4:1-13 (doi: 10.4108/eai.12-9-2016.151678)
Tạp chí: EAI Endorsed Transactions on Context-aware Systems and Applications
Số tạp chí 6(2016) Trang: 1548-1555
Tạp chí: Journal of Electrical Engineering & Technology
Số tạp chí 1(2016) Trang: 9-13
Tạp chí: IJCDM
Số tạp chí 36(2016) Trang: 513–523
Tạp chí: Opuscula Mathematica

Crossref DOI of CTUJoS


BC thường niên 2018


Con số ấn tượng (VN | EN)


Bản tin ĐHCT


TCKH tiếng Việt


TCKH tiếng Anh

 
 
Vui lòng chờ...