Steiner <i>k</i>-edge connected subgraph polyhedra

作     者：Biha, MD Mahjoub, AR 

作者机构：Ecole Polytech Gerad Montreal PQ H3C 3A7 Canada Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Univ Clermont Ferrand 2 LIMOS F-63177 Clermont Ferrand France 

出 版 物：《JOURNAL OF COMBINATORIAL OPTIMIZATION》 (组合优化杂志)

年 卷 期：2000年第4卷第1期

页      面：131-144页

核心收录：

学科分类：12[管理学] 120202[管理学-企业管理（含：财务管理、市场营销、人力资源管理）] 0202[经济学-应用经济学] 02[经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：k-edge connected subgraph polytope series-parallel graph cut facet 

摘      要：In this paper we consider the Steiner k-edge survivable network problem. We discuss the polytope associated with the solutions to that problem. We show that when the graph is series-parallel and k is even, the polytope is completely described by the trivial constraints and the so called Steiner-cut constraints. This generalizes recent work of Baiou and Mahjoub, SIAM J. Discrete Mathematics, vol. 10, pp. 505-514, 1997 for the case k = 2. As a consequence, we obtain in this case a linear description of the polyhedron associated with the problem when multiple copies of an edge are *** this paper we consider the Steiner k-edge survivable network problem. We discuss the polytope associated with the solutions to that problem. We show that when the graph is series-parallel and k is even, the polytope is completely described by the trivial constraints and the so called Steiner-cut constraints. This generalizes recent work of Baiou and Mahjoub, SIAM J. Discrete Mathematics, vol. 10, pp. 505-514, 1997 for the case k = 2. As a consequence, we obtain in this case a linear description of the polyhedron associated with the problem when multiple copies of an edge are allowed.