On the maximum cardinality cut problem in proper interval graphs and related graph classes

DOI10.1016/j.tcs.2021.10.014OpenAlexW3208550523MaRDI QIDQ2055967

Tınaz Ekim, Mordechai Shalom, Arman Boyacı

Publication date: 1 December 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2006.03856

zbMATH Keywords

maximum cutclique-widthproper interval graphclique decompositionbubble model

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• Minimal classes of graphs of unbounded clique-width
• On rigid circuit graphs
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Decomposition by clique separators
• A short proof that `proper = unit'
• Maximum cut on line and total graphs
• The maximum cardinality cut problem in co-bipartite chain graphs
• Clique-width of full bubble model graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A new representation of proper interval graphs with an application to clique-width
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Parameterized Algorithms

This page was built for publication: On the maximum cardinality cut problem in proper interval graphs and related graph classes