Polyhedral study of the connected subgraph problem

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

doi:10.1016/j.disc.2014.08.026

Polyhedral study of the connected subgraph problem

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

Science & Math

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	80-92
Number of pages	13
Journal	Discrete Mathematics
Volume	338
DOIs	https://doi.org/10.1016/j.disc.2014.08.026
State	Published - Jan 6 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier B.V.

Keywords

Connected subgraph
Matching
Partition
Polytope
Separation

Publisher link

10.1016/j.disc.2014.08.026

Find It

Find It at U of M Libraries

Cite this

@article{2dca1e0c773444cca1f55fcf9ebb4b4a,

title = "Polyhedral study of the connected subgraph problem",

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, Matching, Partition, Polytope, Separation",

author = "{Didi Biha}, Mohamed and Kerivin, {Herv{\'e} L.M.} and Ng, {Peh H.}",

note = "Publisher Copyright: {\textcopyright} 2014 Elsevier B.V.",

year = "2015",

month = jan,

day = "6",

doi = "10.1016/j.disc.2014.08.026",

language = "English (US)",

volume = "338",

pages = "80--92",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Polyhedral study of the connected subgraph problem

AU - Didi Biha, Mohamed

AU - Kerivin, Hervé L.M.

AU - Ng, Peh H.

PY - 2015/1/6

Y1 - 2015/1/6

N2 - 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.

AB - 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.

KW - Connected subgraph

KW - Matching

KW - Partition

KW - Polytope

KW - Separation

UR - http://www.scopus.com/inward/record.url?scp=84908190502&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84908190502&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2014.08.026

DO - 10.1016/j.disc.2014.08.026

M3 - Article

AN - SCOPUS:84908190502

SN - 0012-365X

VL - 338

SP - 80

EP - 92

JO - Discrete Mathematics

JF - Discrete Mathematics

ER -

Polyhedral study of the connected subgraph problem

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this