A NETWORK DESIGN PROBLEM WITH TWO-EDGE MATCHING FAILURES


Sharifov F., KUTUCU H.

RAIRO-OPERATIONS RESEARCH, cilt.49, ss.297-312, 2015 (SCI İndekslerine Giren Dergi)

  • Cilt numarası: 49 Konu: 2
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1051/ro/2014038
  • Dergi Adı: RAIRO-OPERATIONS RESEARCH
  • Sayfa Sayısı: ss.297-312

Özet

In this paper, we introduce a network design problem with two-edge matching failures. Given a graph, any two edges non-incident to the same node form a two-edge matching. The problem consists in finding a minimum-cost subgraph such that, when deleting any two-edge matching of the graph, every pair of terminal nodes remains connected. We give mixed integer linear programming formulations for the problem and propose a heuristic algorithm based on the Branch-and-Bound method to solve it. We also present computational results.