Facets of the Bipartite Subgraph Polytope
From MaRDI portal
Publication:3699730
DOI10.1287/moor.10.2.340zbMath0578.05056OpenAlexW2021320246MaRDI 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 problempolyhedral combinatoricsbipartite subgraphsfacet defining inequalitiesfacets of polytopesbicycle wheels
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Polytopes and polyhedra (52B99)
Related Items
The partition problem, Facets of the \(k\)-partition polytope, The equipartition polytope. I: Formulations, dimension and basic facets, The equipartition polytope. II: Valid inequalities and facets, The max-cut problem on graphs not contractible to \(K_ 5\), Maximum bipartite subgraphs of Kneser graphs, The Boolean quadratic polytope: Some characteristics, facets and relatives, On cutting-plane proofs in combinatorial optimization, Small bipartite subgraph polytopes, The minimum chromatic violation problem: a polyhedral approach, On the polyhedral structure of uniform cut polytopes, On the bond polytope, A new global algorithm for max-cut problem with chordal sparsity, A polyhedral study of lifted multicuts, Solving VLSI design and DNA sequencing problems using bipartization of graphs, Cardinality constrained combinatorial optimization: complexity and polyhedra, Polyhedral results for the bipartite induced subgraph problem, Chvátal closures for mixed integer programming problems, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Generating facets for the cut polytope of a graph by triangular elimination, Transitive packing, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, The inequicut cone, The even and odd cut polytopes, Max-cut in circulant graphs, From equipartition to uniform cut polytopes: extended polyhedral results, Pseudo-Boolean optimization, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, Semidefinite relaxations for partitioning, assignment and ordering problems, Semidefinite relaxations for partitioning, assignment and ordering problems, On fractional cut covers, On the cut polytope, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Engineering Branch-and-Cut Algorithms for the Equicut Problem, On some weakly bipartite graphs, Fractional covering by cuts, \(K_ i\)-covers. I: Complexity and polytopes, A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
