U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited

DOI10.4230/LIPICS.MFCS.2020.57MaRDI QIDQ5089227zbMATH OpenFDO

Authors

Publication date 18 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2020.57

zbMATH Keywords

bubble modelclique widthinterval graphsmaxcut problemmixed unit interval graphssubexponential algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited

Cites work

• A new representation of proper interval graphs with an application to clique-width
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Clique-width is NP-complete
• Clique-width minimization is NP-hard
• Finding Hamiltonian circuits in interval graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Labeling Chordal Graphs: Distance Two Condition
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimal classes of graphs of unbounded clique-width
• Mixed unit interval graphs
• Notes on complexity of packing coloring
• On the clique-width of some perfect graph classes
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s
• Subexponential algorithms for unique games and related problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The maximum cardinality cut problem in co-bipartite chain graphs
• The Roberts characterization of proper and unit interval graphs
• Unit interval graphs of open and closed intervals
• Unit mixed interval graphs

Cited in

(8)

• 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
• Intersection graphs of non-crossing paths
• Maximum cut on interval graphs of interval count four is NP-complete
• 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: U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited

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