Polyhedral study of the connected subgraph problem |
| |
Authors: | Mohamed Didi Biha,Hervé L.M. Kerivin,Peh H. Ng |
| |
Affiliation: | 1. LMNO - CNRS UMR 6139, Université de Caen Basse Normandie, Caen, France;2. Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA;3. Division of Science and Mathematics, University of Minnesota - Morris, Morris, MN 56267, USA |
| |
Abstract: | In this paper, we study the connected subgraph polytope which is the convex hull of the solutions to a related combinatorial optimization problem called the maximum weight connected subgraph problem. We strengthen a cut-based formulation by considering some new partition inequalities for which we give necessary and sufficient conditions to be facet defining. Based on the separation problem associated with these inequalities, we give a complete polyhedral characterization of the connected subgraph polytope on cycles and trees. |
| |
Keywords: | Connected subgraph Polytope Matching Partition Separation |
本文献已被 ScienceDirect 等数据库收录! |
|