http://www.cnr.it/ontology/cnr/individuo/prodotto/ID7337

Shiftable Intervals (Articolo in rivista)

Type

Label

Anno

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

Alternative label

MALUCELLI Federico; NICOLOSO Sara (2007)
Shiftable Intervals
in Annals of operations research (Dordr., Online); Kluwer, Dordrecht (Paesi Bassi)
(literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

Pagina inizio

Pagina fine

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

Rivista

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo

Note

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

Titolo

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. (literal)

Editore