On some weakly bipartite graphs

DOI10.1016/0167-6377(83)90031-7zbMath0549.90087OpenAlexW2055365041MaRDI QIDQ800231

Francisco Barahona

Publication date: 1983

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(83)90031-7

zbMATH Keywords

polyhedral combinatoricsellipsoid methodmax- cut problemminimum two-commodity cutweakly bipartite graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10) Polytopes and polyhedra (52Bxx)

Related Items

Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Compositions in the bipartite subgraph polytope, On cuts and matchings in planar graphs, Optimal cuts in graphs and statistical mechanics, Laplacian eigenvalues and the maximum cut problem

Cites Work

• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• The ellipsoid method and its consequences in combinatorial optimization
• Weakly bipartite graphs and the max-cut problem
• The matroids with the max-flow min-cut property
• Facets of the Bipartite Subgraph Polytope
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the cut polytope
• Blocking and anti-blocking pairs of polyhedra
• Multi-Commodity Network Flows