Online ISSN:1349-8606
Progress in Informatics  
No.10 March 2013  
Page 167-174 PDF(1328KB) | References
doi:10.2201/NiiPi.2013.10.10
An efficient exact algorithm for the Minimum Latency Problem
Ha BANG BAN1, Kien NGUYEN2, Manh CUONG NGO3 and Duc NGHIA NGUYEN4
1,3,4Hanoi University of Science and Technology
2National Institute of Informatics
(Received: June 25,2012)
(Revised: October 1,2012)
(Accepted: December 4,2012)
Abstract:
The Minimum Latency Problem (MLP) is a class of combinational optimization problems that has many practical applications. In the general case, the MLP is proved to be NP-hard. One of the approaches to solve the problem is using exact algorithms. However, the algorithms which were recently proposed are applied only to the problems with small size, i.e., 26 vertices. In this paper, we present a new exact algorithm to solve the MLPs with a larger size. Our algorithm is based on the branch and bound method and it has two new rules that improve the pruning technique. We have evaluated the algorithm on several data sets. The results show that the problems up to 40 vertices can be solved exactly.
Keywords:
Minimum Latency Problem (MLP), exact algorithm, branch and bound method
PDF(1328KB) | References

National Institute of Informatics is a member of CrossRef.
Go back HOME