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

## Primary tabs

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 | http://hdl.handle.net/2078/17179 |

## References Provided by I4OC

- Baïou, M., Barahona, F., Mahjoub, A.R.: Separation of Partition Inequalities. Mathematics of Operations Research 25 (2), 243–254, May 2000
- Barahona, F.: Separating from the dominant of the spanning tree polytope. Op. Research Letters 12, 201–203 (1992)
- Barahona, F., Mahjoub, A.R.: On two-connected subgraph polytopes. Discrete Mathematics 147, 19–34 (1995)
- Chopra, S.: The k-edge connected spanning subgraph polyhedron. SIAM Journal on Discrete Mathematics 7, 245–259 (1994)
- Cunningham W.H.: Optimal attack and reinforcement of a network. Journal of ACM 32, 549–561 (1985)
- Didi Biha, M., Mahjoub, A.R.: k-edge connected polyhedra on series-parallel graphs. Operations Research Letters 19, 71–78 (1996)
- Fortz B.: Design of Survivable Networks with Bounded Rings. Vol. 2 Network Theory and Applications. Kluwer Academic Publishers, 2000
- Fortz, B., Labbé, M., Maffioli, F.: Solving the Two-Connected Network with Bounded Meshes Problem. Operations Research, 48 (6), 866–877 November-December 2000
- Fortz B., Labbé M.: Polyhedral results for two-connected networks with bounded rings. Mathematical Programming 93 (1), 27–54 2002
- 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
- Fortz, B., Labbé, M.: Two-connected networks with rings of bounded cardinality. Computational Optimization and Applications 27, 123–148 2004
- Goldberg Andrew V., Tarjan Robert E.,
*A new approach to the maximum-flow problem*, 10.1145/48014.61051 - Gomory, R.E., Hu, T.C.: Multi-Terminal Network Flows. SIAM Journal on Applied Mathematics 9 (4), 551–570, December 1961
- Gourdin, E., Liau, B.: Personnal Communication 2003
- 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
- Gusfield, D.: Very Simple Methods for All Pairs Network Flow Analysis. SIAM Journal on Computing 19 (1), 143–155 February 1990
- 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
- Itai, A., Perl, Y., Shiloach, Y.: The Complexity of Finding Maximum Disjoint Paths with Length Constraints. Networks 12, 277–286 (1982)
- Kerivin, H., Mahjoub, A.R.: Design of Survivable Networks: A Survey. To appear in Networks 2004
- 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
- Mahjoub, A.R.: Two-edge connected spanning subgraphs and polyhedra. Mathematical Programming 64, 199–208 1994
- McCormick, S.T.: Personnal Communication 2001
- Tsong-Ho Wu.: Fiber Network Service Survivability. Artech House Inc. 1992
- Williamson, D.P.: Lecture Notes on Approximation Algorithms. IBM Research Division 1999