| Issue |
RAIRO-Oper. Res.
Volume 49, Number 2, April-May 2015
New challenges in scheduling theory
|
|
|---|---|---|
| Page(s) | 297 - 312 | |
| DOI | https://doi.org/10.1051/ro/2014038 | |
| Published online | 18 December 2014 | |
A Network Design Problem with Two-Edge Matching Failures
1 V.M. Glushkov Institute of Cybernetics, National Academy of
Sciences of Ukraine, 40 Prospekt Akademika Glushkova, 03187 Kiev, Ukraine.
hakankutucu@iyte.edu.tr
2 Department of Computer Engineering,
Karabuk University, 78050
Karabuk,
Turkey
Received:
22
July
2013
Accepted:
17
July
2014
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.
Mathematics Subject Classification: 68M10 / 90C05 / 90C27 / 90B10
Key words: Network design problem / linear programming / Branch-and-Bound method / matching
© EDP Sciences, ROADEF, SMAI 2014
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.