Two-edge connected spanning subgraphs and polyhedra

Two-edge connected spanning subgraphs and polyhedra

0.00 Avg rating0 Votes
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:
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.