Thông tin chung: Ngày nhận bài: 31/03/2020 Ngày nhận bài sửa: 09/06/2020 Ngày duyệt đăng: 28/08/2020 Title: Connected p-median problem on complete graphs and complete bipartite graphs Từ khóa: Bài toán p-median, đồ thị đầy đủ, đồ thị lưỡng phân đầy đủ, thuật toán thời gian tuyến tính Keywords: P-median problem, complete graph, complete partite graph, linear-time algorithm | 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. 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 đủ. |