An experimental study of minimum routing cost spanning tree algorithms

Author

Quoc Phan Tan ; Nghia Nguyen Due

Author_Institution

Dept. of Inf. Technol., Saigon Univ., Ho Chi Minn City, Vietnam

fYear

2013

fDate

15-18 Dec. 2013

Firstpage

158

Lastpage

165

Abstract

The task of finding the Minimum Routing Cost Spanning Tree (MRCST) can be found in many network design problems. In general cases, MRCST problem is a NP-hard problem. Till now, several algorithms for solving the problem are proposed and their performance were evaluated on different data sets. This paper presents a short survey of well known MRCST algorithms and gives a report on an extensive experimentation based on benchmark instances collected from the literature. In addition, the paper is also the first pioneering research that experiment on graphs with up to 1000 vertices.

Keywords

optimisation; performance evaluation; trees (mathematics); MRCST algorithm; NP-hard problem; minimum routing cost spanning tree algorithm; network design problem; performance evaluation; Approximation algorithms; Approximation methods; Encoding; Heuristic algorithms; Routing; Sociology; Statistics; approximation scheme; exact algorithms; heuristic; metaheuristic; minimum routing cost spanning tree; swarm intelligence;

fLanguage

English

Publisher

ieee

Conference_Titel

Soft Computing and Pattern Recognition (SoCPaR), 2013 International Conference of

Conference_Location

Hanoi

Print_ISBN

978-1-4799-3399-0

Type

conf

DOI

10.1109/SOCPAR.2013.7054119

Filename

7054119