Nordic Journal of Computing Bibliography

Hans L. Bodlaender and Klaus Jansen. On the Complexity of the Maximum Cut Problem. Nordic Journal of Computing, 7(1):14-31, Spring 2000.

The complexity of the SIMPLE MAX CUT problem is investigated for several special classes of graphs. It is shown that this problem is NP-complete when restricted to one of the following classes: chordal graphs, undirected path graphs, split graphs, tripartite graphs, and graphs that are the complement of a bipartite graph. The problem can be solved in polynomial time, when restricted to graphs with bounded treewidth, or cographs. We also give large classes of graphs that can be seen as generalizations of classes of graphs with bounded treewidth and of the class of cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.

Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.2 [Discrete Mathematics]

Additional Key Words and Phrases: max cut, graph algorithms, chordal graphs, treewidth, graph decomposition, cographs

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database