Compositions in the bipartite subgraph polytope

DOI10.1016/0012-365X(92)90133-ZzbMath0771.05092OpenAlexW2034300764MaRDI QIDQ1199475

Jean Fonlupt, Jean-Pierre Uhry, Ali Ridha Mahjoub

Publication date: 16 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90133-z

zbMATH Keywords

polynomial time algorithmmax-cut problembipartite subgraph polytopeedge weights

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Related Items

Applications of cut polyhedra. II, One-node cutsets and the dominating set polytope, Solving VLSI design and DNA sequencing problems using bipartization of graphs, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Approximating Unique Games Using Low Diameter Graph Decomposition, On a composition of independence systems by circuit identification, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, On cuts and matchings in planar graphs, Composition of graphs and the triangle-free subgraph polytope, A characterization of weakly bipartite graphs, Laplacian eigenvalues and the maximum cut problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• On some weakly bipartite graphs
• Experiments in quadratic 0-1 programming
• Matroids and multicommodity flows
• The ellipsoid method and its consequences in combinatorial optimization
• Weakly bipartite graphs and the max-cut problem
• Compositions in the bipartite subgraph polytope
• Facets for the cut cone. I
• Facets for the cut cone. II: Clique-web inequalities
• Über eine Eigenschaft der ebenen Komplexe
• Facets of the Bipartite Subgraph Polytope
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• Binary group and Chinese postman polyhedra
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Clique-Web Facets for Multicut Polytopes
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Compositions of Graphs and Polyhedra II: Stable Sets
• On the cut polytope
• Node-and edge-deletion NP-complete problems