Shiftable intervals

Federico Malucelli () and Sara Nicoloso ()

Annals of Operations Research, 2007, vol. 150, issue 1, 137-157

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. Copyright Springer Science+Business Media, LLC 2007

Keywords: Interval graphs; Optimization problems; Complexity (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-006-0161-1 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:150:y:2007:i:1:p:137-157:10.1007/s10479-006-0161-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-006-0161-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().