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

DOI10.1016/J.IPL.2017.01.007MaRDI QIDQ509888zbMATH OpenOpenAlexFDO

Authors Arman Boyacı, Mordechai Shalom, 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

graph algorithmsmaximum cutproper interval graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1496855
• The maximum cardinality cut problem in co-bipartite chain graphs
• A polynomial algorithm for the k-cluster problem on the interval graphs
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs

Cites work

• A new representation of proper interval graphs with an application to clique-width
• A short proof that `proper = unit'
• Algorithmic lower bounds for problems parameterized by clique-width
• Characterizations of derived graphs
• Difference graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Maximum cut on line and total graphs
• Node-Deletion Problems on Bipartite Graphs
• On the clique-width of some perfect graph classes
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s

Cited in

(13)

• The maximum cardinality cut problem in co-bipartite chain graphs
• 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
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
• A polynomial algorithm for the k-cluster problem on the interval graphs
• U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs
• Maximum cut on interval graphs of interval count four is NP-complete
• scientific article; zbMATH DE number 7724211 (Why is no real title available?)
• Complexity of maximum cut on interval graphs
• Canonical cuts of path powers
• Complexity of maximum cut on interval graphs
• Triangles improve 0.878 approximation for Maxcut

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q509888)