\(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
type: Item
instance of: scholarly article
title: \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
author: Yanyan Li
published in: Algorithmica
publication date: 2022-01-18T00:00:00Z
full work available at URL: https://arxiv.org/abs/2002.08311
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7458815
MaRDI profile type: Publication
OpenAlex ID: W3197988729
cites work: Subexponential Algorithms for Unique Games and Related Problems
cites work: SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
cites work: The maximum cardinality cut problem in co-bipartite chain graphs
cites work: Graph Classes: A Survey
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Mixed unit interval graphs
cites work: Clique-width minimization is NP-hard
cites work: Clique-Width is NP-Complete
cites work: Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
cites work: The Roberts characterization of proper and unit interval graphs
cites work: Q3070232
cites work: Q3328583
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Labelling Graphs with a Condition at Distance 2
cites work: A new representation of proper interval graphs with an application to clique-width
cites work: A Characterization of Mixed Unit Interval Graphs
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Notes on complexity of packing coloring
cites work: Q5089227
cites work: Integral mixed unit interval graphs
cites work: Minimal classes of graphs of unbounded clique-width
cites work: Finding Hamiltonian circuits in interval graphs
cites work: Clique-width of full bubble model graphs
cites work: Unit Interval Graphs of Open and Closed Intervals
cites work: Q5588432
cites work: Q3898496
cites work: Labeling Chordal Graphs: Distance Two Condition
cites work: Unit Mixed Interval Graphs
cites work: Completion of the Mixed Unit Interval Graphs Hierarchy
DOI: 10.1007/S00453-021-00837-4
Recommended article: Q5089227
Recommended article: On the maximum cardinality cut problem in proper interval graphs and related graph classes
Recommended article: SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
Recommended article: The \(p\)-Maxian problem on interval graphs
Recommended article: \textsc{max-cut} and containment relations in graphs
Recommended article: Q6087208
Recommended article: Length-bounded cuts: proper interval graphs and structural parameters
Recommended article: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
Recommended article: The Maximum Clique Problem in Multiple Interval Graphs (Extended Abstract)
Recommended article: On graphs of the cone decompositions for the min-cut and max-cut problems
description: scientific article; zbMATH DE number 7458815