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