Title: An approximate solution method based on tabu search for k-minimum spanning tree problems

Authors: Hideki Katagiri, Tomohiro Hayashida, Ichiro Nishizaki, Jun Ishimatsu

Addresses: Department of Artificial Complex Systems Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1, Kagamiyama, Higashi-Hiroshima, 739-8527, Japan. ' Department of Artificial Complex Systems Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1, Kagamiyama, Higashi-Hiroshima, 739-8527, Japan. ' Department of Artificial Complex Systems Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1, Kagamiyama, Higashi-Hiroshima, 739-8527, Japan. ' Department of Artificial Complex Systems Engineering, Graduate School of Engineering, Hiroshima University, 1-4-1, Kagamiyama, Higashi-Hiroshima, 739-8527, Japan

Abstract: This paper considers a new tabu search-based approximate solution algorithm for k-minimum spanning tree problems. One of the features of the proposed algorithm is that it efficiently obtains local optimal solutions without applying minimum spanning tree algorithms. Numerical experimental results show that the proposed method provides a good performance especially for dense graphs in terms of solution accuracy over existing algorithms.

Keywords: k-minimum spanning tree; k-MST; tabu search; approximate solutions; dense graphs.

DOI: 10.1504/IJKESDP.2010.035908

International Journal of Knowledge Engineering and Soft Data Paradigms, 2010 Vol.2 No.3, pp.263 - 274

Published online: 08 Oct 2010 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article