User menu

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

Bibliographic reference Fortz, Bernard ; Pesneau, Pierre ; Mc Cormick S., Thomas ; Mahjoub Ali, Ridha. Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut. In: Mathematical Programming, Vol. 105, no. 1, p. 85-111 (2005)
Permanent URL
  1. Baïou, M., Barahona, F., Mahjoub, A.R.: Separation of Partition Inequalities. Mathematics of Operations Research 25 (2), 243–254, May 2000
  2. Barahona, F.: Separating from the dominant of the spanning tree polytope. Op. Research Letters 12, 201–203 (1992)
  3. Barahona, F., Mahjoub, A.R.: On two-connected subgraph polytopes. Discrete Mathematics 147, 19–34 (1995)
  4. Chopra, S.: The k-edge connected spanning subgraph polyhedron. SIAM Journal on Discrete Mathematics 7, 245–259 (1994)
  5. Cunningham W.H.: Optimal attack and reinforcement of a network. Journal of ACM 32, 549–561 (1985)
  6. Didi Biha, M., Mahjoub, A.R.: k-edge connected polyhedra on series-parallel graphs. Operations Research Letters 19, 71–78 (1996)
  7. Fortz B.: Design of Survivable Networks with Bounded Rings. Vol. 2 Network Theory and Applications. Kluwer Academic Publishers, 2000
  8. Fortz, B., Labbé, M., Maffioli, F.: Solving the Two-Connected Network with Bounded Meshes Problem. Operations Research, 48 (6), 866–877 November-December 2000
  9. Fortz B., Labbé M.: Polyhedral results for two-connected networks with bounded rings. Mathematical Programming 93 (1), 27–54 2002
  10. Fortz, B., Mahjoub, A.R., McCormick, S.T., Pesneau, P.: Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut. Working paper 98/03 Institut d'Administration et de Gestion Universtié Catholique de Louvain, Belgique, 2003
  11. Fortz, B., Labbé, M.: Two-connected networks with rings of bounded cardinality. Computational Optimization and Applications 27, 123–148 2004
  12. Goldberg Andrew V., Tarjan Robert E., A new approach to the maximum-flow problem, 10.1145/48014.61051
  13. Gomory, R.E., Hu, T.C.: Multi-Terminal Network Flows. SIAM Journal on Applied Mathematics 9 (4), 551–570, December 1961
  14. Gourdin, E., Liau, B.: Personnal Communication 2003
  15. Grötschel, M., Monma, C.L., Stoer, M.: Design of Survivable Networks. chapter 10, pp. 617–672. Handbooks in Operations Research and Management Science. Elsevier, North-Holland Amsterdam. 1995
  16. Gusfield, D.: Very Simple Methods for All Pairs Network Flow Analysis. SIAM Journal on Computing 19 (1), 143–155 February 1990
  17. Hao, J., Orlin, J. B.: A faster algorithm for finding the minimum cut in a graph. Proc. of 3rd ACM-SIAM Symp. on Discrete Algorithms 1992, pp. 165–174
  18. Itai, A., Perl, Y., Shiloach, Y.: The Complexity of Finding Maximum Disjoint Paths with Length Constraints. Networks 12, 277–286 (1982)
  19. Kerivin, H., Mahjoub, A.R.: Design of Survivable Networks: A Survey. To appear in Networks 2004
  20. Ladányi, L., Ralphs, T.K., Trotter, L.E.: Computational Combinatorial Optimization: Optimal or Provably Near-Opimal Solutions. Branch Cut and Price: Sequential and Parallel 223–260. Lecture Notes in Computer Science. Springer-Verlag, September 2001
  21. Mahjoub, A.R.: Two-edge connected spanning subgraphs and polyhedra. Mathematical Programming 64, 199–208 1994
  22. McCormick, S.T.: Personnal Communication 2001
  23. Tsong-Ho Wu.: Fiber Network Service Survivability. Artech House Inc. 1992
  24. Williamson, D.P.: Lecture Notes on Approximation Algorithms. IBM Research Division 1999