A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
type: Item
instance of: scholarly article
title: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
zbMATH Open document ID: 1404.68081
author: Arman Boyacı
author: Mordechai Shalom
author: Tınaz Ekim
published in: Information Processing Letters
publication date: 2017-02-21T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6687381
zbMATH Keywords: graph algorithms
zbMATH Keywords: maximum cut
zbMATH Keywords: proper interval graph
MaRDI profile type: Publication
full work available at URL: j.ipl.2017.01.007
OpenAlex ID: W2584187496
cites work: Q4500843
cites work: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
cites work: Maximum cut on line and total graphs
cites work: Finding a Maximum Cut of a Planar Graph in Polynomial Time
cites work: Q5417642
cites work: Characterizations of derived graphs
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
cites work: A new representation of proper interval graphs with an application to clique-width
cites work: Node-Deletion Problems on Bipartite Graphs
cites work: Difference graphs
cites work: Q5503435
cites work: A short proof that `proper = unit'
DOI: 10.1016/J.IPL.2017.01.007
description: scientific article; zbMATH DE number 6687381