Shiftable intervals |
| |
Authors: | Federico Malucelli Sara Nicoloso |
| |
Institution: | (1) Dipartimento di Elettronica e Informazione - Politecnico di Milano, Via Ponzio 34/5, 20133 Milano, Italy;(2) IASI-CNR, Viale Manzoni 30, 00185 Roma, Italy |
| |
Abstract: | Consider a set of n fixed length intervals and a set of n (larger) windows, in one-to-one correspondence with the intervals, and assume that each interval can be placed in any position
within its window. If the position of each interval has been fixed, the intersection graph of such set of intervals is an
interval graph. By varying the position of each interval in all possible ways, we get a family of interval graphs. In the
paper we define some optimization problems related to the clique, stability, chromatic, clique cover numbers and cardinality
of the minimum dominating set of the interval graphs in the family, mainly focussing on complexity aspects, bounds and solution
algorithms. Some problems are proved to be NP-hard, others are solved in polynomial time on some particular classes of instances.
Many practical applications can be reduced to these kind of problems, suggesting the use of Shiftable Intervals as a new interesting
modeling framework. |
| |
Keywords: | Interval graphs Optimization problems Complexity |
本文献已被 SpringerLink 等数据库收录! |
|