Geodesic
A Network Design Problem with Two-Edge Matching Failures
Sharifov, Firdovsi1 ; Kutucu, Hakan2
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, 40 Prospekt Akademika Glushkova, 03187 Kiev, Ukraine.
2 Department of Computer Engineering, Karabuk University, 78050 Karabuk, Turkey
RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 297-312

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2014038
Classification : 68M10, 90C05, 90C27, 90B10
Keywords: Network design problem, linear programming, Branch-and-Bound method, matching

Sharifov, Firdovsi 1 ; Kutucu, Hakan 2

1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, 40 Prospekt Akademika Glushkova, 03187 Kiev, Ukraine.
2 Department of Computer Engineering, Karabuk University, 78050 Karabuk, Turkey 
@article{RO_2015__49_2_297_0,
     author = {Sharifov, Firdovsi and Kutucu, Hakan},
     editor = {Blazewicz, Jacek and Pesch, Erwin and Philipps, Cynthia and Trystram, Denis and Zhang, Guochuan},
     title = {A {Network} {Design} {Problem} with {Two-Edge} {Matching} {Failures}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {297--312},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {2},
     year = {2015},
     doi = {10.1051/ro/2014038},
     zbl = {1328.90020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2014038/}
}
TY  - JOUR
AU  - Sharifov, Firdovsi
AU  - Kutucu, Hakan
ED  - Blazewicz, Jacek
ED  - Pesch, Erwin
ED  - Philipps, Cynthia
ED  - Trystram, Denis
ED  - Zhang, Guochuan
TI  - A Network Design Problem with Two-Edge Matching Failures
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2015
SP  - 297
EP  - 312
VL  - 49
IS  - 2
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2014038/
DO  - 10.1051/ro/2014038
LA  - en
ID  - RO_2015__49_2_297_0
ER  - 
%0 Journal Article
%A Sharifov, Firdovsi
%A Kutucu, Hakan
%E Blazewicz, Jacek
%E Pesch, Erwin
%E Philipps, Cynthia
%E Trystram, Denis
%E Zhang, Guochuan
%T A Network Design Problem with Two-Edge Matching Failures
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2015
%P 297-312
%V 49
%N 2
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2014038/
%R 10.1051/ro/2014038
%G en
%F RO_2015__49_2_297_0
Sharifov, Firdovsi; Kutucu, Hakan. A Network Design Problem with Two-Edge Matching Failures. RAIRO - Operations Research - Recherche Opérationnelle, New challenges in scheduling theory, Tome 49 (2015) no. 2, pp. 297-312. doi: 10.1051/ro/2014038

Cité par Sources :