Article ID: | iaor19961318 |
Country: | Netherlands |
Volume: | 64 |
Issue: | 2 |
Start Page Number: | 199 |
End Page Number: | 208 |
Publication Date: | Apr 1994 |
Journal: | Mathematical Programming (Series A) |
Authors: | Mahjoub Ali Ridha |
This paper studies the probelm of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. The paper discusses the polytope associated with the solutions to this problem. It shows that when the graph is series-parallel the polytope is completely described by the trivial constraints and the so-called cut constraints. The paper also gives some classes of facet defining inequalities of this polytope when the graph is general.