Maximum cut on interval graphs of interval count four is NP-complete

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)

zbMATH Keywords

maximum cutNP-completeinterval graphsinterval countinterval lengths

Mathematics Subject Classification ID

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