Weakly bipartite graphs and the Max-cut problem |
| |
Authors: | M Grtschel |
| |
Institution: | Institut für Operations Research, Universität Bonn, Nassestr. 2, D-5300 Bonn 1, Fed. Rep. Germany;Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada |
| |
Abstract: | 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 of even length. |
| |
Keywords: | Max-cut problem bipartite graphs planar graphs ellipsoid method shortest paths |
本文献已被 ScienceDirect 等数据库收录! |
|