Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142540 | Operations Research Letters | 2010 | 4 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Laura Galli, Adam N. Letchford,