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 đủ.

Trích dẫn: Nguyễn Ngọc Đăng Duy và Võ Nguyễn Minh Hiếu, 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 Trường Đại học Cần Thơ. 56(4A): 26-32.