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

DOI10.1016/j.ipl.2017.01.007zbMath1404.68081OpenAlexW2584187496MaRDI QIDQ509888

Mordechai Shalom, Arman Boyacı, Tınaz Ekim

Publication date: 21 February 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.01.007

zbMATH Keywords

maximum cutgraph algorithmsproper interval graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

Maximum cut on interval graphs of interval count four is NP-complete ⋮ Complexity of maximum cut on interval graphs ⋮ Unnamed Item ⋮ On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• A short proof that `proper = unit'
• Maximum cut on line and total graphs
• A new representation of proper interval graphs with an application to clique-width
• Node-Deletion Problems on Bipartite Graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Characterizations of derived graphs
• Difference graphs

This page was built for publication: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs