ĐỀ XUẤT THUẬT TOÁN MỚI GIẢI BÀI TOÁN CÂY KHUNGVỚI CHI PHÍ ĐỊNH TUYẾN NHỎ NHẤT TRONG TRƯỜNG HỢP ĐỒ THỊ THƯA

Abstract

Minimum routing cost spanning tree problem - MRCST is a graph optimization problem that has many applications in network communication design and bioinformatics. The MRCST problem is proved to be NP-hard. Most graphs in practical are sparse graphs while the most effective algorithm solving MRCST on sparse graph is not really effective - especially with sparse graphs in large size. This paper proposes a new algorithm called HCST to solve the MRCST problem for sparse graphs. The experimental results in sparse graphs taken from the experimental data system benchmark for optimal spanning tree problems show that the quality of HCST algorithm is equal or better than that of the best algorithms known to solve MRCST in time comparison. This is also the first publication which presents theexperimental results from solving MRCST for 20 large size sparse graphs instances.

Tóm tắt

Bài toán cây khung với chi phí định tuyến nhỏ nhất (Minimum Routing Cost Spanning Tree - MRCST) là bài toán tối ưu đồ thị có nhiều ứng dụng trong lĩnh vực thiết kế mạng truyền thông và trong tin sinh học; đây là bài toán thuộc lớp NP-hard. Hầu hết các đồ thị gặp trong thực tế ứng dụng là đồ thị thưa, trong khi các thuật toán hiệu quả nhất hiện biết giải bài toán MRCST trên đồ thị thưa chưa thực sự hiệu quả - nhất là với các đồ thị thưa có kích thước lớn. Bài báo này đề xuất một thuật toán mới với tên gọi HCST để giải bài toán MRCST trong trường hợp đồ thị thưa. Kết quả thực nghiệm trên các đồ thị thưa trong hệ thống dữ liệu thực nghiệm chuẩn cho thấy thuật toán HCST cho chất lượng lời giải tương đương hoặc tốt hơn và với thời gian tính nhanh hơn khi so với các thuật toán tốt nhất hiện biết. Bài báo này cũng là công trình đầu tiên công bố kết quả thực nghiệm giải bài toán MRCST cho 20 bộ dữ liệu là các đồ thị thưa có kích thước lớn.