Recognizing unit multiple interval graphs is hard

DOI10.1016/J.DAM.2024.09.011MaRDI QIDQ6648267zbMATH OpenFDO

Authors Virginia Ardévol Martínez, Romeo Rizzi, Florian Sikora, Stéphane Vialette

Publication date 4 December 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2024.09.011

zbMATH Keywords

interval graphsNP-hardnessrecognitionunit multiple interval graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
• Recognizing d-interval graphs and d-track interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• The maximum clique problem in multiple interval graphs
• The maximum clique problem in multiple interval graphs (extended abstract)

Cites work

• 34th international symposium on algorithms and computation (ISAAC 2023), Kyoto, Japan, December 3--6, 2023
• A short proof that `proper = unit'
• A special planar satisfiability problem and a consequence of its NP- completeness
• A unified approach to approximating resource allocation and scheduling
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• Extremal Values of the Interval Number of a Graph
• scientific article; zbMATH DE number 3877239 (Why is no real title available?)
• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• On double and multiple interval graphs
• On Restrictions of Balanced 2-Interval Graphs
• On the computational complexity of 2-interval pattern matching problems
• On the parameterized complexity of multiple-interval graph problems
• Open-interval graphs versus closed-interval graphs
• Optimization problems in multiple-interval graphs
• Parameterized algorithms
• Recognizing d-interval graphs and d-track interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• Representation of a finite graph by a set of intervals on the real line
• Scheduling Split Intervals
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of induced minors and related problems
• The Complexity of the Partial Order Dimension Problem
• The LBFS structure and recognition of interval graphs
• The maximum clique problem in multiple interval graphs
• Topics in Intersection Graph Theory
• Unit interval graphs of open and closed intervals

This page was built for publication: Recognizing unit multiple interval graphs is hard

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