Tabu Search Heuristics for Two Bounded Degree Spanning Tree Problems

ÖNCAN T.

15th IFAC Symposium on Information Control Problems in Manufacturing, Ottawa, Kanada, 11 - 13 Mayıs 2015, cilt.48, ss.1167-1172 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 48
  • Doi Numarası: 10.1016/j.ifacol.2015.06.242
  • Basıldığı Şehir: Ottawa
  • Basıldığı Ülke: Kanada
  • Sayfa Sayıları: ss.1167-1172
  • Galatasaray Üniversitesi Adresli: Evet

Özet

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.