THUẬT TOÁN PHÂN LUỒNG ĐA PHƯƠNG TIỆN TUYẾN TÍNH TỐI ƯU TRÊN MẠNG GIAO THÔNG MỞ RỘNG

Tóm tắt

Đồ thị và mạng mở rộng là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. [7]. Kết quả chính của bài báo là nghiên cứu phát triển thuật toán tìm luồng đa phương tiện tuyến tính tối ưu trên mạng giao thông mở rộng, dựa trên cơ sở sử dụng thuật toán tìm luồng đa phương tiện tuyến tính cực đại đồng thời chi phí cực tiểu trên mạng giao thông mở rộng [8]. Đây là thuật toán tính gần đúng với tỉ lệ xấp xỉ là (1 + ) với  dương nhỏ tùy ý. Bài báo phân tích, chứng minh các kết quả đưa ra cũng như đánh giá độ phức tạp của thuật toán. Chương trình thuật toán được viết bằng ngôn ngữ Java với cơ sở dữ liệu mạng mở rộng cài đặt trong hệ quản trị cơ sở dữ liệu MySQL cho kết quả chính xác.