Weakly bipartite graphs and the max-cut problem
M Grötschel, WR Pulleyblank - Operations research letters, 1981 - Elsevier
A new class of graphs, called weakly bipartite graphs, is introduced. A graph is called
weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related
to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class
of bipartite graphs and the class of planar graphs. It is shown that the max-cut problem can
be solved in polynomial time for weakly bipartite graphs. The polynomical algorithm
presented is based on the ellipsoid method and an algorithm that computes a shortest path …
weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related
to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class
of bipartite graphs and the class of planar graphs. It is shown that the max-cut problem can
be solved in polynomial time for weakly bipartite graphs. The polynomical algorithm
presented is based on the ellipsoid method and an algorithm that computes a shortest path …
[PDF][PDF] Weakly bipartite graphs and the max-cut problem
MGWR Pulleyblank - Oper. Res. Lett, 1981 - academia.edu
A new class of graphs, called weakly bipartite graphs, is introduced. A graph is called
weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related
to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class
bf bipartitc graphs and the class of planar graphs. It is shown that the max-cut problem can
be solved in polynomial time for weakly bipartite graphs. The polynomial algorithm
presented is based on the ellipsoid method and an algorithm that computes a shortest path …
weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related
to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class
bf bipartitc graphs and the class of planar graphs. It is shown that the max-cut problem can
be solved in polynomial time for weakly bipartite graphs. The polynomial algorithm
presented is based on the ellipsoid method and an algorithm that computes a shortest path …
以上显示的是最相近的搜索结果。 查看全部搜索结果