Maximum cut on interval graphs of interval count four is NP-complete
From MaRDI portal
Publication:6124829
DOI10.1007/s00454-023-00508-xMaRDI QIDQ6124829
Alexsander A. de Melo, Celina M. Herrera de Figueiredo, Unnamed Author, Fabiano S. Oliveira
Publication date: 2 April 2024
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- On counting interval lengths of interval graphs
- A linear-time algorithm for proper interval graph recognition
- Simple linear time recognition of unit interval graphs
- Interval graphs and interval orders
- Some simplified NP-complete graph problems
- On the sum coloring problem on interval graphs
- On the classes of interval graphs of limited nesting and count of lengths
- Optimal labelling of unit interval graphs
- Revising Johnson's table for the 21st century
- A short proof of the NP-completeness of minimum sum interval coloring
- Computing Minimum Geodetic Sets of Proper Interval Graphs
- The NP-completeness column: an ongoing guide
- Optimal Linear Arrangement of Interval Graphs
- Complexity of maximum cut on interval graphs
This page was built for publication: Maximum cut on interval graphs of interval count four is NP-complete