On the Steiner 2-edge connected subgraph polytope

A. Rhida Mahjoub; Pierre Pesneau

RAIRO - Operations Research (2008)

  • Volume: 42, Issue: 3, page 259-283
  • ISSN: 0399-0559

Abstract

top
In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge connected subgraph problem in that class of graphs.

How to cite

top

Mahjoub, A. Rhida, and Pesneau, Pierre. "On the Steiner 2-edge connected subgraph polytope." RAIRO - Operations Research 42.3 (2008): 259-283. <http://eudml.org/doc/250431>.

@article{Mahjoub2008,
abstract = { In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge connected subgraph problem in that class of graphs. },
author = {Mahjoub, A. Rhida, Pesneau, Pierre},
journal = {RAIRO - Operations Research},
keywords = {Polytope; Steiner 2-edge connected graph; Halin graph.; polytope; Halin graph},
language = {eng},
month = {8},
number = {3},
pages = {259-283},
publisher = {EDP Sciences},
title = {On the Steiner 2-edge connected subgraph polytope},
url = {http://eudml.org/doc/250431},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Mahjoub, A. Rhida
AU - Pesneau, Pierre
TI - On the Steiner 2-edge connected subgraph polytope
JO - RAIRO - Operations Research
DA - 2008/8//
PB - EDP Sciences
VL - 42
IS - 3
SP - 259
EP - 283
AB - In this paper, we study the Steiner 2-edge connected subgraph polytope. We introduce a large class of valid inequalities for this polytope called the generalized Steiner F-partition inequalities, that generalizes the so-called Steiner F-partition inequalities. We show that these inequalities together with the trivial and the Steiner cut inequalities completely describe the polytope on a class of graphs that generalizes the wheels. We also describe necessary conditions for these inequalities to be facet defining, and as a consequence, we obtain that the separation problem over the Steiner 2-edge connected subgraph polytope for that class of graphs can be solved in polynomial time. Moreover, we discuss that polytope in the graphs that decompose by 3-edge cutsets. And we show that the generalized Steiner F-partition inequalities together with the trivial and the Steiner cut inequalities suffice to describe the polytope in a class of graphs that generalizes the class of Halin graphs when the terminals have a particular disposition. This generalizes a result of Barahona and Mahjoub [4] for Halin graphs. This also yields a polynomial time cutting plane algorithm for the Steiner 2-edge connected subgraph problem in that class of graphs.
LA - eng
KW - Polytope; Steiner 2-edge connected graph; Halin graph.; polytope; Halin graph
UR - http://eudml.org/doc/250431
ER -

References

top
  1. M. Baïou, Le problème du sous-graphe Steiner 2-arête connexe: approche polyédrale. Ph.D. thesis, Université de Rennes 1 (1996).  
  2. M. Baïou, F. Barahona and A.R. Mahjoub, Separation of partition inequalities. Math. Oper. Res.25 (2000) 243–254.  
  3. M. Baïou and A.R. Mahjoub, Steiner 2-edge connected subgraph polytopes on series-parallel graphs. SIAM J. Discrete Math.10 (1997) 505–514.  
  4. F. Barahona and A.R. Mahjoub, On two-connected subgraph polytopes. Discrete Math.147 (1995) 19–34.  
  5. D. Bienstock, E.F. Brickell and C.L. Monma, On the structure of minimum-weight k-connected spanning networks. SIAM J. Discrete Math.3 (1990) 320–329.  
  6. S.C. Boyd and T. Hao, An integer polytope related to the design of survivable communication networks. SIAM J. Discrete Math.6 (1993) 612–630.  
  7. S. Chopra, The k-edge connected spanning subgraph polyhedron. SIAM J. Discrete Math.7 (1994) 245–259.  
  8. N. Christofides and C.A. Whitlock, Network synthesis with connectivity constraints: a survey, in Operational Research 81, Hamburg edited by J.P. Brans (1981) 705–723.  
  9. G. Cornuéjols, J. Fonlupt and D. Naddef, The traveling salesman problem on a graph and some related integer polyhedra. Math. program.33 (1985) 1–27.  
  10. R. Coullard, A. Rais, R.L. Rardin and D.K. Wagner, Linear-time algorithm for the 2-connected Steiner subgraph problem on special classes of graphs. Networks23 (1993) 195–206.  
  11. R. Coullard, A. Rais, R.L. Rardin and D.K. Wagner, The dominant of the 2-connected steiner subgraph polytope for W4-free graphs. Discrete Appl. Math.66 (1996) 33–43.  
  12. M. Didi Biha and A.R. Mahjoub, k-edge connected polyhedra on series-parallel graphs. Oper. Res. Lett.19 (1996) 71–78.  
  13. M. Didi Biha and A.R. Mahjoub, The k-edge connected subgraph problem I: Polytopes and critical extreme points. Linear Algebra Appl.381 (2004) 117–139.  
  14. R.E. Erikson, C.L. Monma, and Jr. A.F. Veinott, Send and split method for a minimum-concave-cost network flows. Math. Oper. Res.12 (1987) 634–664.  
  15. J. Fonlupt and A.R. Mahjoub, Critical extreme points of the 2-edge connected subgraph polytope, in Integer Programming and Combinatorial Optimization: 7th International IPCO Conference, edited by G. Cornuéjols, R.E. Burkard and G.J. Woeginger, Lect. Notes Comput. Sci. Graz, Austria, Springer-Verlag 1610 (1999) 166–183.  
  16. J. Fonlupt and A.R. Mahjoub, Critical extreme points of the 2-edge connected spanning subgraph polytope. Math. Program.105 (2006) 289–310.  
  17. J. Fonlupt and D. Naddef, The traveling salesman problem in graphs with some excluded minors. Math. Program.53 (1992) 147–172.  
  18. M. Grötschel and C. Monma, Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J. Discrete Math.3 (1990) 502–523.  
  19. M. Grötschel, C. Monma and M. Stoer, Polyhedral approaches to network survivability, in Reliability of computer and Communication Networks, edited by F. Hwang F. Roberts and C. Monma, Series Discrete Math. Comput. Sci.5 (1991) 121–141 AMS/ACM.  
  20. M. Grötschel, C. Monma and M. Stoer, Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Oper. Res.40 (1992) 309–330.  
  21. M. Grötschel, C. Monma and M. Stoer, Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM J. Optim.2 (1992) 474–504.  
  22. M. Grötschel, C.L. Monma and M. Stoer, Design of Survivable Networks, in Network Models, Handbooks in Operations Research and Management Science, Elsevier, North-Holland, Amsterdam, Vol. 7, chapter 10 (1995) 617–672.  
  23. R. Halin, Studies on minimality n-connected graphs. In Combinatorial Math. Appl., edited by J.A. Welsh, Academic Press, New York (1971) 129–136.  
  24. H. Kerivin, Réseaux fiables et polyèdres. Ph.D. thesis, Université de Clermont Ferrand II, France (2000).  
  25. H. Kerivin and A.R. Mahjoub, Design of survivable networks: A survey. Networks46 (2005) 1–21.  
  26. H. Kerivin, A.R. Mahjoub and C. Nocq, (1,2)-survivable networks: Facets and branch-and-cut, in The Sharpest Cut, edited by M. Grötschel, MPS-SIAM Series in Optimization (2004) 121–152.  
  27. H. Kerivin and A. Ridha Mahjoub, On survivable network polyhedra. Discrete Math.290 (2005) 183–210.  
  28. A.R. Mahjoub, Two-edge connected spanning subgraphs and polyhedra. Math. Program.64 (1994) 199–208.  
  29. A.R. Mahjoub and P. Pesneau, On the Steiner 2-edge connected subgraph polytope. Technical Report RR-06:02, LIMOS, Université Blaise Pascal, Clermont-Ferrand, France (2006).  
  30. C. Monma, B. Munson and W. Pulleyblank, Minimum-weight two-connected spanning networks. Math. Program.46 (1990) 153–171.  
  31. W.R. Pulleyblank, Polyhedral Combinatorics, OR & MS, in Optimization, volume 1, North Holland, Amsterdam (1989) 371–446.  
  32. K. Steiglitz, P. Weinen and D.J. Kleitmann, The design of minimum cost survivable networks. IEEE Trans. Circuit Theory16 (1969) 455–460.  
  33. S. Voss, Steiner-probleme in graphen. Math. Systems in Economics (1990).  
  34. P. Winter, Generalized Steiner problem in Halin graphs, in Proceedings of the 12th International Symposium on Math. Program. MIT (1985).  
  35. P. Winter, Generalized Steiner problem in series-parallel networks. J. Algor.7 (1986) 549–566.  

NotesEmbed ?

top

You must be logged in to post comments.