Polyhedral study of the connected subgraph problem

Mohamed Didi Biha, Hervé L.M. Kerivin, Peh H. Ng

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)80-92
Number of pages13
JournalDiscrete Mathematics
Volume338
DOIs
StatePublished - Jan 6 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier B.V.

Keywords

  • Connected subgraph
  • Matching
  • Partition
  • Polytope
  • Separation

Fingerprint

Dive into the research topics of 'Polyhedral study of the connected subgraph problem'. Together they form a unique fingerprint.

Cite this