A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs

BaşlıkA polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
Publication TypeJournal Article
Year of Publication2017
AuthorsBoyacı, A., T. Ekim, and M. Shalom
JournalInformation Processing Letters
Volume121
Pagination29-33
ISSN0020-0190
Anahtar kelimelerGraph algorithms, Maximum cut, Proper interval graph
Abstract

It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.
URLhttps://www.sciencedirect.com/science/article/pii/S0020019017300133
DOI10.1016/j.ipl.2017.01.007