\(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
From MaRDI portal
Publication:2067672
DOI10.1007/s00453-021-00837-4OpenAlexW3197988729MaRDI QIDQ2067672
Publication date: 18 January 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.08311
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Integral mixed unit interval graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Clique-width of full bubble model graphs
- 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
- Labelling Graphs with a Condition at Distance 2
- Graph Classes: A Survey
- 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
This page was built for publication: \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
