scientific article; zbMATH DE number 7559428

DOI10.4230/LIPIcs.MFCS.2020.57MaRDI QIDQ5089227

No author found.

Publication date: 18 July 2022

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

interval graphssubexponential algorithmmaxcut problemclique widthbubble modelmixed unit interval graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Maximum cut on interval graphs of interval count four is NP-complete ⋮ Complexity of maximum cut on interval graphs ⋮ Intersection graphs of non-crossing paths ⋮ 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
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• Minimal classes of graphs of unbounded clique-width
• Mixed unit interval graphs
• Finding Hamiltonian circuits in interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Notes on complexity of packing coloring
• The maximum cardinality cut problem in co-bipartite chain graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• The Roberts characterization of proper and unit interval graphs
• A new representation of proper interval graphs with an application to clique-width
• Clique-width minimization is NP-hard
• A Characterization of Mixed Unit Interval Graphs
• Completion of the Mixed Unit Interval Graphs Hierarchy
• Subexponential Algorithms for Unique Games and Related Problems
• Clique-Width is NP-Complete
• Labeling Chordal Graphs: Distance Two Condition
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Unit Interval Graphs of Open and Closed Intervals
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Unit Mixed Interval Graphs