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

ApproximationInterval graphsInverse chromatic number problemInverse combinatorial optimizationMachine(s)-scheduling with earliness and or tardiness costsNP-hardness

Mathematics Subject Classification ID

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

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 combinatorial optimization: a survey on problems, methods, and results
• Inverse Optimization
• 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 traveling salesman problems
• On inverse chromatic number problems (extended abstract)
• Inverse chromatic number problems in interval and permutation graphs
• Notes on inverse bin-packing 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)