Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs

DOI10.1007/978-3-540-77891-2_17MaRDI QIDQ5452164zbMATH OpenOpenAlexFDO

Authors Yerim Chung, Jean-François Culus, 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) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Inverse chromatic number problems in interval and permutation graphs
• On inverse chromatic number problems (extended abstract)
• Inverting the Turán problem with chromatic number
• On the interval chromatic number of proper interval graphs
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• On \(n\)-inverse domination number in graphs
• scientific article; zbMATH DE number 5823945
• On incompactness for chromatic number of graphs
• scientific article; zbMATH DE number 3908459
• The Domatic Number Problem in Interval Graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3550186 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Inverse Optimization
• Inverse combinatorial optimization: a survey on problems, methods, and results
• Non-approximability of just-in-time scheduling
• One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Single-machine scheduling of unit-time jobs with earliness and tardiness penalties
• Some Inverse Traveling Salesman Problems
• The 0-1 inverse maximum stable set problem
• The complexity analysis of the inverse center location problem

Cited in

(4)

• On inverse chromatic number problems (extended abstract)
• Inverse chromatic number problems in interval and permutation graphs
• Notes on inverse bin-packing problems
• On inverse traveling salesman problems

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

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