On the maximum cardinality cut problem in proper interval graphs and related graph classes
type: Item
instance of: scholarly article
title: On the maximum cardinality cut problem in proper interval graphs and related graph classes
author: Arman Boyacı
author: Tınaz Ekim
author: Mordechai Shalom
published in: Theoretical Computer Science
publication date: 2021-12-01T00:00:00Z
full work available at URL: https://arxiv.org/abs/2006.03856
full work available at URL: https://hdl.handle.net/11729/3306
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 7437220
zbMATH Keywords: maximum cut
zbMATH Keywords: proper interval graph
zbMATH Keywords: clique decomposition
zbMATH Keywords: clique-width
zbMATH Keywords: bubble model
MaRDI profile type: Publication
OpenAlex ID: W3208550523
cites work: Q4500843
cites work: SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
cites work: A short proof that `proper = unit'
cites work: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
cites work: Parameterized Algorithms
cites work: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
cites work: On rigid circuit graphs
cites work: Fundamentals of parameterized complexity
cites work: The maximum cardinality cut problem in co-bipartite chain graphs
cites work: Q5417642
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Maximum cut on line and total graphs
cites work: Finding a Maximum Cut of a Planar Graph in Polynomial Time
cites work: A new representation of proper interval graphs with an application to clique-width
cites work: Q5089227
cites work: Minimal classes of graphs of unbounded clique-width
cites work: Clique-width of full bubble model graphs
cites work: Decomposition by clique separators
DOI: 10.1016/J.TCS.2021.10.014
description: scientific article; zbMATH DE number 7437220