PHÁT HIỆN CÁC CHU TRÌNH CHƯA BẢO HÒA CƯỚC PHÍ ÂM

 

Trần Thị Huệ Nương, Trần Kỳ Phùng, Hữu Ngọc

Khoa Toán – Tin, Trường Đại học Khoa học Tự Nhiên

 

Tóm tắt:

 

Bài báo  cung cấp thuật toán phát hiện các chu trình chưa bảo hoa cước phí âm, giúp cho giải bài toán dòng trên mạng rất dễ dàng.

 

 

 

 

 

 

 

 

 

 

 

 

 

THE NEGATIVE COST UNSATURATED CYCLE

 

Tran Thi Hue Nuong, Tran Ky Phung, Huu Ngoc

University of Natural Sciences

Abstract

 

In this paper we consider a special type of linear programming problem called the minimum-cost network flow problem and give the algorithm to find the negative cost unsaturated cycle.