A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
From MaRDI portal
Publication:509888
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
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