The maximum clique problem in multiple interval graphs

DOI10.1007/s00453-013-9828-6zbMath1325.68107arXiv1201.0043OpenAlexW2045135589MaRDI QIDQ2350898

Mathew C. Francis, Pascal Ochem, Daniel Gonçalves

Publication date: 25 June 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.0043

zbMATH Keywords

NP-completenessmaximum cliqueapproximation hardness\(t\)-interval graphs\(t\)-track graphsunit \(t\)-interval graphsunit \(t\)-track graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (7)

On edge intersection graphs of paths with 2 bends ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ On Edge Intersection Graphs of Paths with 2 Bends ⋮ Temporal interval cliques and independent sets ⋮ Combinatorial problems on \(H\)-graphs ⋮ On \(H\)-topological intersection graphs ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• Approximation algorithms for intersection graphs
• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Recognizing graphs with fixed interval number is NP-complete
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• On the parameterized complexity of multiple-interval graph problems
• Optimization, approximation, and complexity classes
• The max clique problem in classes of string-graphs
• Transversals of \(d\)-intervals
• The Clique Problem in Ray Intersection Graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Vertex Intersection Graphs of Paths on a Grid
• On double and multiple interval graphs
• On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Universality considerations in VLSI circuits
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On approximation properties of the Independent set problem for degree 3 graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Scheduling Split Intervals
• Algorithms – ESA 2005
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: The maximum clique problem in multiple interval graphs