Home > Research > Publications & Outputs > Small bipartite subgraph polytopes

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

Small bipartite subgraph polytopes

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Small bipartite subgraph polytopes. / Galli, L; Letchford, A N.
In: Operations Research Letters, Vol. 38, No. 5, 2010, p. 337-340.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Galli, L & Letchford, AN 2010, 'Small bipartite subgraph polytopes', Operations Research Letters, vol. 38, no. 5, pp. 337-340. https://doi.org/10.1016/j.orl.2010.05.004

APA

Galli, L., & Letchford, A. N. (2010). Small bipartite subgraph polytopes. Operations Research Letters, 38(5), 337-340. https://doi.org/10.1016/j.orl.2010.05.004

Vancouver

Galli L, Letchford AN. Small bipartite subgraph polytopes. Operations Research Letters. 2010;38(5):337-340. doi: 10.1016/j.orl.2010.05.004

Author

Galli, L ; Letchford, A N. / Small bipartite subgraph polytopes. In: Operations Research Letters. 2010 ; Vol. 38, No. 5. pp. 337-340.

Bibtex

@article{9a413f9c92a741e8a5c22aa1b73c4718,
title = "Small bipartite subgraph polytopes",
abstract = "We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes.",
keywords = "polyhedral combinatorics, max-cut problem, integrality ratios",
author = "L Galli and Letchford, {A N}",
year = "2010",
doi = "10.1016/j.orl.2010.05.004",
language = "English",
volume = "38",
pages = "337--340",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "5",

}

RIS

TY - JOUR

T1 - Small bipartite subgraph polytopes

AU - Galli, L

AU - Letchford, A N

PY - 2010

Y1 - 2010

N2 - We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes.

AB - We compute a complete linear description of the bipartite subgraph polytope, for up to seven nodes, and a conjectured complete description for eight nodes. We then show how these descriptions were used to compute the integrality ratio of various relaxations of the max-cut problem, again for up to eight nodes.

KW - polyhedral combinatorics

KW - max-cut problem

KW - integrality ratios

U2 - 10.1016/j.orl.2010.05.004

DO - 10.1016/j.orl.2010.05.004

M3 - Journal article

VL - 38

SP - 337

EP - 340

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 5

ER -