Two-edge connected spanning subgraphs and polyhedra |
| |
Authors: | Ali Ridha Mahjoub |
| |
Institution: | (1) Department of Statistics and Operations Research, College of Sciences, King Saud University, Riyadh, Saudi Arabia;(2) Present address: Laboratoire d'Informatique de Brest (LIBr), Université de Bretagne Occidentale, 6 avenue Le Gorgeu, 29287 Brest cedex, France |
| |
Abstract: | This paper studies the problem 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. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general.Research supported in part by the Natural Sciences and Engineering Research Council of Canada and CP Rail and the German Research Association (Deutsche Forschungsgemeinschaft SFR 303). |
| |
Keywords: | Two-edge connected graphs Polyhedra Facets Series— parallel graphs |
本文献已被 SpringerLink 等数据库收录! |
|