Bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ

Nguyễn Ngọc Đăng Duy * và Võ Nguyễn Minh Hiếu

* Tác giả liên hệ (duy3300@gmail.com)

Article Sidebar

Full Text: PDF

Ngày nhận bài: 31-03-2020
Ngày duyệt đăng: 28-08-2020
Ngày xuất bản: 28-08-2020
Title: Connected p-median problem on complete graphs and complete bipartite graphs
DOI: 10.22144/ctu.jvn.2020.079
Lượt xem
77
Downloads
67
Crossref
Scopus
Google Scholar
Europe PMC
Trích dẫn
Duy, N. N. Đ., & Hiếu, V. N. M. (2020). Bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ. Tạp chí Khoa học Đại học Cần Thơ, 56(4), 26-32. https://doi.org/10.22144/ctu.jvn.2020.079
Số báo
Tập. 56 Số. 4 (2020)
Chuyên mục
Tự nhiên

Abstract

In this paper, a connected p-median problem on complete graphs and complete bipartite graphs is mentioned. To solve this problem, several theorems and lemmas are given during research. Besides, linear-time algorithms are developed to solve the connected p-median problem on complete graphs and complete bipartite graphs.
Keywords: P-median problem, complete graph, complete partite graph, linear-time algorithm

Tóm tắt

Trong bài báo này, một bài toán vị trí liên quan đến các thành phần liên thông trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ được đề cập. Để giải quyết bài toán này, một số định lí và bổ đề được đưa ra trong quá trình nghiên cứu. Bên cạnh đó, các thuật toán thời gian tuyến tính được đưa ra để giải bài toán liên thông p-median trên đồ thị đầy đủ và đồ thị lưỡng phân đầy đủ.
Từ khóa: bài toán p-median, đồ thị lưỡng phân đầy đủ, đồ thị đầy đủ, thuật toán thời gian tuyến tính

Article Details

Tài liệu tham khảo

Bondy, J.A. ,and Murty, U.S.R. , 1976. Graph theory with applications. The Macmillan Press Ltd. Great Britain, 264 pages.

Chang, S.C., Yen, W.C.K., Wang, Y.L., and Liu, J.J., 2015. The connected p-median problem on block graphs. Springer – Verlag.

Hoare, C.A.R., 1961. Algorithm 65: Find .Communications of the ACM, 4(7): 321–322.

Kang, L., Zhou, J. and Shan, E., 2018 Algorithms for connected p-centdianproblem on block graphs. J Comb Optim, 36(1): 252–263.

Kariv, O., and Hakimi, S.L., 1979. An algorithmic approach to network location problems, II. The p-medians. SIAM Journal on Applied Mathematics, 37(3): 539-560.

Krarup, J., and Vajda, S., 1997. On Torricelli’s geometrical solution to a problem of Fermat IMA Journal of Mathematics Applied in Business and Industry, 8(3): 215–224.