Facets of the Bipartite Subgraph Polytope
From MaRDI portal
Publication:3699730
DOI10.1287/moor.10.2.340zbMath0578.05056MaRDI QIDQ3699730
Martin Grötschel, Francisco Barahona, Ali Ridha Mahjoub
Publication date: 1985
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.10.2.340
max-cut problem; polyhedral combinatorics; bipartite subgraphs; facet defining inequalities; facets of polytopes; bicycle wheels
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
05C85: Graph algorithms (graph-theoretic aspects)
52B99: Polytopes and polyhedra
Related Items
Transitive packing, On the cut polytope, Semidefinite relaxations for partitioning, assignment and ordering problems, Semidefinite relaxations for partitioning, assignment and ordering problems, On the polyhedral structure of uniform cut polytopes, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Cardinality constrained combinatorial optimization: complexity and polyhedra, From equipartition to uniform cut polytopes: extended polyhedral results, The max-cut problem on graphs not contractible to \(K_ 5\), Small bipartite subgraph polytopes, The inequicut cone, The even and odd cut polytopes, Pseudo-Boolean optimization, On some weakly bipartite graphs, Chvátal closures for mixed integer programming problems, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, \(K_ i\)-covers. I: Complexity and polytopes, A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound, Maximum bipartite subgraphs of Kneser graphs, The Boolean quadratic polytope: Some characteristics, facets and relatives, On cutting-plane proofs in combinatorial optimization, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, Max-cut in circulant graphs, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Facets of the \(k\)-partition polytope, The partition problem, Polyhedral results for the bipartite induced subgraph problem, Generating facets for the cut polytope of a graph by triangular elimination, The equipartition polytope. I: Formulations, dimension and basic facets, The equipartition polytope. II: Valid inequalities and facets, Engineering Branch-and-Cut Algorithms for the Equicut Problem, Fractional covering by cuts
