On the complexity of the maximum cut problem

Hans Bodlaender; Klaus Jansen

doi:10.1007/3-540-57785-8_189

On the complexity of the maximum cut problem

Hans Bodlaender, Klaus Jansen

Decision Support Systems

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

Abstract

The complexity of the SIMPLE MAXCUT 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 the cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.

Original language	English
Title of host publication	STACS 94
Subtitle of host publication	11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24–26, 1994 Proceedings
Editors	Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner
Publisher	Springer
Pages	769-780
Number of pages	12
Volume	775
ISBN (Electronic)	978-3-540-48332-8
ISBN (Print)	978-3-540-57785-0
DOIs	https://doi.org/10.1007/3-540-57785-8_189
Publication status	Published - 1994

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/3-540-57785-8_189

http://dx.doi.org/10.1007/3-540-57785-8_189

Cite this

Bodlaender, H., & Jansen, K. (1994). On the complexity of the maximum cut problem. In P. Enjalbert, E. W. Mayr, & K. W. Wagner (Eds.), STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24–26, 1994 Proceedings (Vol. 775, pp. 769-780). (Lecture Notes in Computer Science). Springer. https://doi.org/10.1007/3-540-57785-8_189

@inbook{e482c8fbfb2d4d7d8c26c2b6b9519150,

title = "On the complexity of the maximum cut problem",

abstract = "The complexity of the SIMPLE MAXCUT 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 the cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.",

author = "Hans Bodlaender and Klaus Jansen",

year = "1994",

doi = "10.1007/3-540-57785-8_189",

language = "English",

isbn = "978-3-540-57785-0",

volume = "775",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "769--780",

editor = "Patrice Enjalbert and Mayr, {Ernst W.} and Wagner, {Klaus W.}",

booktitle = "STACS 94",

}

On the complexity of the maximum cut problem. / Bodlaender, Hans; Jansen, Klaus.
STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science Caen, France, February 24–26, 1994 Proceedings. ed. / Patrice Enjalbert; Ernst W. Mayr; Klaus W. Wagner. Vol. 775 Springer, 1994. p. 769-780 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - On the complexity of the maximum cut problem

AU - Bodlaender, Hans

AU - Jansen, Klaus

PY - 1994

Y1 - 1994

N2 - The complexity of the SIMPLE MAXCUT 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 the cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.

AB - The complexity of the SIMPLE MAXCUT 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 the cographs, and allow polynomial time algorithms for the SIMPLE MAX CUT problem.

U2 - 10.1007/3-540-57785-8_189

DO - 10.1007/3-540-57785-8_189

M3 - Chapter

SN - 978-3-540-57785-0

VL - 775

T3 - Lecture Notes in Computer Science

SP - 769

EP - 780

BT - STACS 94

A2 - Enjalbert, Patrice

A2 - Mayr, Ernst W.

A2 - Wagner, Klaus W.

PB - Springer

ER -

On the complexity of the maximum cut problem

Abstract

Publication series

Access to Document

Fingerprint

Cite this