Tabu Search Heuristics for Two Bounded Degree Spanning Tree Problems

ÖNCAN T.

15th IFAC Symposium on Information Control Problems in Manufacturing, Ottawa, Canada, 11 - 13 May 2015, vol.48, pp.1167-1172 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 48
  • Doi Number: 10.1016/j.ifacol.2015.06.242
  • City: Ottawa
  • Country: Canada
  • Page Numbers: pp.1167-1172
  • Galatasaray University Affiliated: Yes

Abstract

In this work, we address two variants of the spanning tree problem. The first problem deals with finding a spanning tree such that the number of branch vertices,vertices with degrees of at least three, is minimum (MBV) and the second one involves constructing a spanning tree with minimum sum of branch vertex degrees (MDS). We suggest an attribute based Tabu Search (TS) heuristic approach for both problems. According to extensive computational experiments done on standard test sets, we observe that the TS heuristics outperform the best known heuristics from the literature. (C) 2015, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.