Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs

DOI10.1007/978-3-540-77891-2_17zbMath1132.90372OpenAlexW2126749429MaRDI QIDQ5452164

Jean-François Culus, Yerim Chung, Marc Demange

Publication date: 25 March 2008

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77891-2_17

zbMATH Keywords

NP-hardnessApproximationInterval graphsInverse chromatic number problemInverse combinatorial optimizationMachine(s)-scheduling with earliness and or tardiness costs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

On inverse traveling salesman problems ⋮ Notes on inverse bin-packing problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The 0-1 inverse maximum stable set problem
• Non-approximability of just-in-time scheduling
• The complexity analysis of the inverse center location problem
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Single-Machine Scheduling of Unit-Time Jobs with Earliness and Tardiness Penalties
• Some Inverse Traveling Salesman Problems
• Inverse Optimization
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

This page was built for publication: Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs